In most real-world use of the term, a paradox isn't something that's impossible, it's just something that intuitively seems wrong when you first think about it.

"I got a Prius so now I am spending more money on gas" sounds ridiculous, but it would be an instance of this paradox.