Yeah, this is something that has always bugged be a tiny bit. I was more familiar with the idea of a paradox as something like your definition -- containing an actual contradiction. But it seems to be used instead to describe any initially counterintuitive situation.

It is tempting to attribute this to a technical/non-technical difference (similar to fallacy, which in non-technical discussion has been expanded to basically include almost any bad argument). But somehow the Birthday "Paradox" has managed to stick in probability.