You Should not Expect a Just-So Story
To my eyes, the question reeks of adaptationism: the attempt to explain what we see (cats and dogs, or otherwise) exclusively in terms of evolutionary adaptation, as if all creatures were evolutionary "perfect."
Humoring that, an adaptationist response would read as follows: Domestic pet warfare was emphatically not the problem cat and dog brains evolved to solve. They evolved in the wild: all dogs used to be wolves, and cats had every reason to fear them, and no reason to evolve a method of distinguishing good and bad dogs.
But even that involves some speculation.
Darwin was the first to highlight the difficulty of understanding why a specific trait did or did not evolve (Origin, ch. VII):
Why, in other quarters of the world, various animals belonging to this same order have not acquired either an elongated neck or a proboscis, cannot be distinctly answered; but it is as unreasonable to expect a distinct answer to such a question, as why some event in the history of mankind did not occur in one country, whilst it did in another.
The over-eager application of adaptationism -- making up evolutionary "just so" stories -- has been out of favor among evolutionary biologists since Stephen J. Gould famously criticized it in "The Spandrels of San Marco and the Panglossian Paradigm: A Critique of the Adaptationist Programme", Proc. of the Royal Society of London, Series B, Biological Sciences, 205, 1979.
Evolutionary psychology (which the question involves) has a bad reputation among biologists for being (in many cases) too adaptationist in its assumptions.
Evolution is not guaranteed to produce optimal or general solutions to problems -- i.e. a cat that knows what it should and should not trust. It cobbles together half-assed solutions to very specific problems -- a heuristic like "be afraid of anything snake-like," perhaps -- and it can only use existing material.
As a result, organisms easily get stuck in myriad sub-optimal solutions along the way. What might appear to us as an obvious way around a problem ("Don't waste resources fighting friendly animals") may not at all be obvious to mutation and natural selection! Ergo the famous caricature of evolution as a limited "tinker" rather than a brilliant "engineer" by François Jacob (Cf. "Evolution and Tinkering," Science, vol. 196, 1977)
EDIT: I should not that how often local optimums inhibit ideal adaptation is a very controversial topic in biology. Adaptationism has a strong following today, due in part to the success of evolutionary game theory at using adaptationist assumptions to model animal behavior.