Question

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.