Goldbach's Conjecture.

Granted this is open, so it may be cheating a bit. However, this seems like a very hard problem to intuit your way to the "conventional wisdom". By contrast, P != NP is "obviously" true. Indeed, Feynman had trouble believing P != NP was even open.