Google recognized the problem last week and issued this statement in response to all of the complaints:
Thanks to everyone for responding and confirming that things are back to normal with Gmail IMAP access.
We believe the issue was caused by a combination of changes we made to the way Gmail processes IMAP and the way some mail clients (such as Windows Mobile and Android) handled those changes*.
About 12 hours ago we rolled those changes back and we've patched things up to make sure it doesn't happen in the future.
Thanks for your patience while we got to the bottom of this and our apologies for any inconvenience this issue may have caused.
Ethan
*If you're interested in the technical explanation, check out the posts from Brandon, a Gmail Engineer:
IMAP Servers Down - Gmail Help