There is a whole class of examples of the following general form: There is an obvious candidate for the solution to an optimization problem, and the obvious candidate is in fact best, but it's very hard to prove that it's best. Two of the examples mentioned in the comments—isoperimetric inequalities and sphere packing—fall into this class. Lower bounds in computational complexity furnish other examples, although our knowledge in this area is so pitiful that the best examples are still conjectural.
I like these examples better than the topological ones like the Jordan curve theorem and the invariance of domain, because there is room to argue that (for example) what makes the Jordan curve theorem hard is that modern mathematics has an exceedingly general definition of a Jordan curve that includes monsters that are non-rectifiable, nowhere differentiable, etc. The "man in the street" doesn't have these monsters in mind when judging that the Jordan curve theorem is obvious. In contrast, if we take something like "the kissing number of the sphere is 12," the man-in-the-street's conception of a counterexample is really no different from the mathematician's. It's just that the man in the street will be convinced after a few minutes of playing with velcro balls and the mathematician won't.
