I am experiencingthe same thing. Both my iPhone en my iPad are saying imap.gmail.com not responding since 8.8.12. I tried the following, without luck:
A) delete gmail account and started from zero
B) turning off/on devices
C) accessed gmail 'captcha' page as suggested by other forums/users
D) changed password in gmail (note that I can also access my gmail account from the laptop or the desktop iMac)
E) tried the weird thing of putting imap.googlemail in advanced settings (imap prefix)
It is VERY frustrating. I hope one could find a solution soon.
I forgot to say that I have also tried the two step verification process indicated by @kaykaykay. No luck. Also on 5.1.1, new iPad and iPhone 4s.
Also tried different wifi networks. On the same wifi my wife's iPhone works well. Grrr! As @kaykaykay says, the default process involves no imap prefix (just a slash) and port 993. It is like this now. Well, at least I can access gmail from Safari.....
I am having the exact same problem, I did not change password or mess around with settings. My ipad1, iphone 4s, and macbook pro mail app have all stopped working as of the morning of august 9, 2012. Have tried everything, but nothing seems to work, I can still access gmail from safari.. ***?!?!
i also found the same problem.. and unable to open my gmail account through my iphone.. then i search on the net and find the solution..
if you get the following message "“The user name Or the password for imap.gmail.com is incorrect" How to fix "imap.gmail.com" Gmail error on iPhone,iPad,Android or Mac? it will fix your issue..