What I noticed is that the infamous question "so what?", though seldomly asked directly, can be read in the eyes of the audience every time when the following three (rather common) conditions are satisfied:
a) there is nobody in the audience who ever thought of the question himself
b) there is no catchy picture or phrase in the presentation
c) some non-zero special knowledge is needed to understand even the statement of the theorem.
It doesn't really matter much what kind of result is being presented: a non-existence one, or something else though condition (b) (the only one you really have some control over during the talk) is much harder to violate when you are presenting a non-existence theorem. Indeed, you, apparently, cannot provide a fascinating example of an entity that doesn't exist in mathematics. Neither cannot you conclude with "we still do not understand a lot about the behavior of this fascinating object" when the object does not exist. And the whole thing often looks about as exciting as a report of a treasure hunting expedition that ends up with "so, after spending many days questioning the locals, climbing, digging, etc., we can safely conclude that there has never been anything of value in that area".
Still, one can be impressed with a pure impossibility theorem.
My favorite non-existence result is the impossibility to find an elementary antiderivative of $\frac{e^x}{x}$. It is useless to try to impress a layman with it. The appreciation I have comes from the fact that in my case (a) and (c) were violated.
First, when I was a student our calculus recitation sections consisted for one semester almost exclusively of finding some tricky antiderivatives. Many of those were of the kind where changing a single sign or a coefficient would result in an unsolvable problem and there were some misprints in the assignments. That made me wonder whether it might be possible to solve the problem as given. Of course, our teachers claimed that $\int \sin(x^2)dx$ and such cannot be presented by a neat formula but they never gave us even the slightest hint why. We saw, of course, that no standard integration trick worked but that might merely mean that there are some new tricks to discover. I was smart enough not to try what was claimed to be proven impossible but not smart enough to prove that impossibility or even to have a decent idea about how such things could be proved in general. I thought of asking my teachers about it but I suspected (rightly, as it turned out) that they knew it no better than I and no analysis textbook I was reading gave me the slightest clue.
That was in Russia back in 80's, so you could not just google "Liouville theorem" up or download any fancy book you wanted from the web. So, I remained completely ignorant until much later, when I was a postdoc at MSU, I visited the University of Toledo and met Rao Nagissetti who gave me some papers of his. To my great surprise, those were about impossibility to solve some quadratic differential equations in elementary functions. The old memories returned at once and I read those papers overnight. The ideas were completely novel to me though I have read Lang's algebra by then and wasn't afraid of Galois theory and such; I just viewed all that as something infinitely remote from any analysis question. That was one of the few times in my life when I was genuinely impressed: the proof lay not beyond my technical abilities (it isn't technically difficult at all) but beyond the range my imagination.
I leave it to you to derive a moral from this story (if it has any). I want only to say that I have managed to forget many things I learned but I doubt I'll ever forget the Liouville theorem. I played with it a bit too over the years (See http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2471315#p2471315 for my latest attempt. It also shows that today some kids are as curious about these questions as I was 25 years ago).