It is well-known that the axiom of choice is equivalent to many other assumptions, such as the well-ordering principle, Tychonoff's theorem, and the fact that every vector space has a basis.  Even though all these formulations are equivalent, I have heard many people say that they 'believe' the axiom of choice, but they don't 'believe' the well-ordering principle.  

So, my question is what do you consider to be the most unintuitive application of choice?

Here is the sort of answer that I have in mind.  

An infinite number of people are about to play the following game.  In a moment, they will go into a room and each put on a different hat.  On each hat there will be a real number.  Each player will be able to see the real numbers on all the hats (except their own). After all the hats are placed on, the players have to simultaneously shout out what real number they think is on their own hat.  The players win if only a finite number of them guess incorrectly.  Otherwise, they are all executed. They are not allowed to communicate once they enter the room, but beforehand they are allowed to talk and come up with a strategy (with infinite resources).

The very unintuitive fact is that the players have a strategy whereby they can always win.  Indeed, it is hard to come up with a strategy where at least one player is guaranteed to answer correctly, let alone a co-finite set.  Hint: the solution uses the axiom of choice.  

I have enjoyed the other answers very much. But perhaps it
would be desirable to balance the discussion somewhat with
a counterpoint, by mentioning a few of the
counter-intuitive situations that can occur when the axiom
of choice fails. For although mathematicians often point to
what are perceived as strange consequences of AC, many of
the situations that can arise when one drops the axiom are
also quite bizarre.


There can be a nonempty tree $T$, with no leaves, but which has no infinite
path. That is, every finite path in the tree can be extended one more step, but there is no
path that goes forever.
A real number can be in the closure of a set $X\subset\mathbb{R}$, but
not the limit of any sequence from $X$.
A function $f:\mathbb{R}\to\mathbb{R}$ can be continuous
in the sense that $x_n\to x\Rightarrow f(x_n)\to f(x)$,
but not in the $\epsilon\ \delta$ sense.
A set can be infinite, but have no countably infinite subset.
Thus, it can be incorrect to say that $\aleph_0$ is the smallest infinite
cardinality, since there can be infinite sets of
incomparable size with $\aleph_0$. (see this MO
answer.)
There can be an equivalence relation on $\mathbb{R}$, such that the number of equivalence classes is strictly greater than the size of $\mathbb{R}$. (See François's excellent answer.) This is a consequence of AD, and thus relatively consistent with DC and countable AC.
There can be a field with no algebraic closure.
The rational field $\mathbb{Q}$ can have different nonisomorphic algebraic closures (due to Läuchli, see Timothy Chow's comment below). Indeed, $\mathbb{Q}$ can have an uncountable algebraic closure, as well as a countable one.
There can be a vector space with no basis.
There can be a vector space with bases of different
cardinalities.
The reals can be a countable union of countable
sets.
Consequently, the theory of Lebesgue measure can fail totally.
The first uncountable ordinal $\omega_1$ can be
singular.
More generally, it can be that every uncountable $\aleph_\alpha$ is
singular. Hence, there are no infinite regular uncountable
well-ordered cardinals.
See the Wikipedia
page
for additional examples.

