The halting problem seems kind of important. Also, at least two of Hilbert's problems -- the continuum hypothesis and solving general Diophantine equations --

The halting problem seems kind of important. Also, at least two of Hilbert's problems -- the continuum hypothesis and solving general Diophantine equations -- turned out to be undecidable (the latter because it reduces to the halting problem.) Edit: Er, actually, the Diophantine equation question would be uncomputable (like the halting problem), not undecidable. The ideas are closely related, though.