The following is a comment by John Baez, posted on Google+ where I linked to this thread:

It's indeed hard to believe, at a gut level, in the existence of a well-ordered uncountable set. For example: can you take the set of real numbers and linearly order them in some funny way such that any decreasing sequence of them, say a > b > c > ..., "bottoms out" after finitely many steps? (Here > is defined in the funny way you've chosen.) Nobody knows an explicit way to do this, and you can prove that nobody ever will. Yet the "well-ordering theorem" says you can do it:

http://en.wikipedia.org/wiki/Well-ordering_theorem

What's the catch? This theorem is equivalent to the Axiom of Choice, which cannot be proved (or disproved!) from the rest of the Zermelo-Fraenkel axioms of set theory.

So, we may decide to disbelieve in the Axiom of Choice. But there are other ways of stating it, which make it sound obviously true.