I'm not sure if it is considered obvious, but I think the Collatz conjecture is also a good example (not just hard to prove, but still unproven!). I've always found it very frustrating that such a simple conjecture does not lend itself to a simple proof.
'Obvious' here sort of means: Try a lot of values, and you'll get a feeling THAT it indeed holds, but also WHY it holds.
