A paradox, a paradox, a most ingenious paradox!
I'm a bit of a purist when it comes to paradoxes. I don't consider the most ingenious one to be one. (Autoplaying video warning)
Tem42 defines paradoxes roughly as 'when there are two reasonable ways of looking at something and they result in a contradiction'. I often find myself tempted to be exclusionary to the point of saying 'two [or more] sound arguments with contradictory conclusions' (in which case, paradoxes are logically impossible).
I'm happy to be less exclusive, of course. My main goal is to throw out the birthday 'paradox' and its ilk. (For those who don't know, the BP essentially says 'How many people do I need in a room for there to be a 50% chance that two of them share a birthday. Answer: only 23. That's so low! How very paradoxical!').
The Phantom Menace DVD special features contains a clip of some people asking Jake Lloyd (Anakin Skywalker) how much he'd estimate the film costs to make, and the ten(?)-year-old Jake replies hesitantly 'Probably over 50 000 dollars?'
Would people say that this ten-year-old underestimating the cost of film-making to be an example of a paradox? Technically, this fits the Greek root (contrary to opinion/expectation), but we don't use it that way. So whywhywhy would it be a paradox that people with bad mathematical intuition are surprised by mathematical results? Stupid people get things wrong? PARADOX! No.
Yes, I'll even throw out the Monty Hall paradox. It's bizarre at first glance, but if you look at it correctly, you'll eventually realise it was confusing because you didn't understand it or math properly. Your fault, not the fault of the world, or of logic.
The Sorites Paradox (the heap) may be a paradox, though it's really just clumsy language. The surprise execution seems to be a paradox because, well, let's see you solve it if you think it's not. Same for the 'This sentence is false' and other self-referential paradoxes. If you can solve the paradox with 'People are stupid' I prefer not to count it. If you have to solve it by saying 'Language is broken', I consider counting it. If you can't solve it without saying 'Logic is broken', then we have something I'd consider a paradox.