[jprice]

I had exactly this problem and I have a Windows Live account. The answer is that you must check sync email when initially establishing the email account on the phone. I didn't, initially, and got the same problem. I did a hard reset, then re-established the email account, allowing email syncing, and problem solved.