Banach–Tarski Paradox
en.wikipedia.org
en.wikipedia.org
[1] http://www.irregularwebcomic.net/2339.html [2] http://mathoverflow.net/a/70435
Most of the examples are all the lines of "without the axiom of choice, one could assume X and not reach a contradiction" - you could assume you had an infinite set with no countably infinite subsets etc.
Which is a little different than the OP, which says something must exist. Within reason, more axioms increase the number of things that definitely are the case but fewer axioms increase the number of things that might be the case.
Of course, if one restricts consideration to "measurable sets" and other objects of standard geometry, the paradox can't happen.