I'm having the same problem with my gmail today. I'd be willing to bet that they're having server issues. For now, I'd suggest using gmail.com and hoping the issue clears up.
yes, now it doesn't give that certificate message anymore...
On the other hand, now it hangs for ages, trying to receive new mails, but it never does... It can still send them though.
Oh well, I guess back to gmail.com :/