My GMail IMAP just stopped working this week. It was definitely an issue on the server side since none of my machines could log in. There had been some suspicious activity on my account and I had to change my password. Apparently when that happens, a bit gets flipped turning off your IMAP. Well I asked a question in the Help forms and found out a CAPTCHA gets turned on which is preventing my IMAP from working. To clear it, follow this link.
Clear Your CAPTCHA
It is a mystery to me why GMail doesn't send me an e-mail or something telling me to do this. But anyway, problem solved. Thanks bkennelly from the help forums.