I think that the ergodic theorem is a good example of this. In down-to-earth terms it says that if you have a box full of gas then the average velocity of all of the gas particles at a given time (the space average) equals the average velocity of a single given particle over time (the time average). This can be regarded as at least a partial theoretical justification for the fact that gas in a container reaches an equilibrium state over time. And what could be more obvious than that?
Yet the ergodic theorem revealed itself as frustratingly difficult to prove. You might think that the challenge would be to just come up with the right precise formulation of the problem; indeed, I don't think it was until people started to identify the measure theoretic underpinnings of probability theory that this was really possible. But while any student with a semester of measure theory under his/her belt can understand the modern formulation of the pointwise ergodic theorem, I highly doubt that very many could supply a correct proof without a hint. For some reason, the proof simply demands an ingenious combinatorial trick.