Just to collect some of the comments into an answer:
- Unsolvability of the word problem for groups, that is, there exist groups for which there is no algorithm determining when two elements are equal
- Unsolvability of the general quintic (and unsolvability of particular quintics such as $x^5-x+1=0$) in terms of radicals
- To the Pythagoreans, existence of irrationals (in particular, irrationality of $\sqrt2$)
- Russell's paradox, and in particular, the inconsistency of Frege's set theory
- Rice's theorem that, roughly, all "interesting" questions about programs are undecidable. (The halting problem, the mother of all undecidable problems, is a special case.)
- The category $\sf Top$, whose objects are topological spaces and whose morphisms are continuous functions, is not Cartesian closed, in particular it does not have exponential objects. This motivates the search for "nicer" categories of topological spaces
- Hilbert's tenth problem : there is no algorithm for polynomial Diophantine equations.
- Noneuclidean geometry. In one way, mathematicians were disappointed by the proof that the parallel postulate did not follow from the other more intuitive axioms. That disappointment was clearly tempered by the pleasure in expanding the idea of a geometry.
- The existence of non-measurable sets in set theory with the axiom of choice. (Partly tempered by the Solovay model, a model of set theory without the (full) axiom of choice in which every set is measurable, though I don't know how much working measure theorists care about it.)
- The independence of the continuum hypothesis from ZFC set theory, on the existence of a set of intermediate cardinality between the naturals and the reals. Georg Cantor tried to prove it for many years, and it was Hilbert's first problem in his 1900 address. Gödel proved its consistency with ZFC in 1940, and Cohen proved the consistency of its negation in 1963.
- The Weierstrass function, the first continuous nowhere-differentiable function, got some pretty nasty comments thrown its way
- Arrow's impossibility theorem that, when there are at least three alternatives, there is no ranked voting system (other than dictatorship!) that satisfies two reasonable-sounding conditions. Informally, every ranked voting system sacrifices some form of "fairness".