Do complex numbers really exist?
There are a few good answers to this question, depending on the audience. I've used all of these on occasion.
A way to solve polynomials
We came up with equations like $x - 5 = 0$, what is $x$?, and the naturals solved them (easily). Then we asked, "wait, what about $x + 5 = 0$?" So we invented negative numbers. Then we asked "wait, what about $2x = 1$?" So we invented rational numbers. Then we asked "wait, what about $x^2 = 2$?" so we invented irrational numbers.
Finally, we asked, "wait, what about $x^2 = -1$?" This is the only question that was left, so we decided to invent the "imaginary" numbers to solve it. All the other numbers, at some point, didn't exist and didn't seem "real", but now they're fine. Now that we have imaginary numbers, we can solve every polynomial, so it makes sense that that's the last place to stop.
Pairs of numbers
This explanation goes the route of redefinition. Tell the listener to forget everything he or she knows about imaginary numbers. You're defining a new number system, only now there are always pairs of numbers. Why? For fun. Then go through explaining how addition/multiplication work. Try and find a good "realistic" use of pairs of numbers (many exist).
Then, show that in this system, $(0,1) * (0,1) = (-1,0)$, in other words, we've defined a new system, under which it makes sense to say that $\sqrt{-1} = i$, when $i=(0,1)$. And that's really all there is to imaginary numbers: a definition of a new number system, which makes sense to use in most places. And under that system, there is an answer to $\sqrt{-1}$.
The historical explanation
Explain the history of the imaginary numbers. Showing that mathematicians also fought against them for a long time helps people understand the mathematical process, i.e., that it's all definitions in the end.
I'm a little rusty, but I think there were certain equations that kept having parts of them which used $\sqrt{-1}$, and the mathematicians kept throwing out the equations since there is no such thing.
Then, one mathematician decided to just "roll with it", and kept working, and found out that all those square roots cancelled each other out.
Amazingly, the answer that was left was the correct answer (he was working on finding roots of polynomials, I think). Which lead him to think that there was a valid reason to use $\sqrt{-1}$, even if it took a long time to understand it.
The concept of mathematical numbers and "existing" is a tricky one. What actually "exists"?
Do negative numbers exist? Of course they do not. You can't have a negative number of apples.
Yet, the beauty of negative numbers is that when we define them (rigorously), then all of a sudden we can use them to solve problems we were never ever able to solve before, or we can solve them in a much simpler way.
Imagine trying to do simple physics without the idea of negative numbers!
But are they "real"? Do they "exist"? No, they don't. But they are just tools that help us solve real life problems.
To go back to your question about complex numbers, I would say that the idea that they exist or not has no bearing on whether they are actually useful in solving the problems of every day life, or making them many, many, many times more easy to solve.
The math that makes your computer run involves the tool that is complex numbers, for instance.
No number does "really exist" the way trees or atoms exist. In physics people however have found use for complex numbers just as they have found use for real numbers.