Was having same problem here and though I would post my resolution.
I have an Exchange 2010 environment FWIW and had this issue with 2 iPhone 5 setups. One of them was just set up today and I applied the recent IOS update - the other phone did not (still does not) have the update.
Anyway, the settings that worked for me were not obvious or standard. In Account settings I set as follows:
Email: The usual full email address of the user
Server: fully qualified name e.g. mail.servername.com
Domain: I DID fill this in with our domain name... I know that almost everyone claims this is optional. I filled it in.
Username: I only entered the SHORT name here - NOT the full email address. - e.g. aeinstein NOT aeinstein@domain.com
Password: the user's password
Finally, in my case SSL is enabled / S/MIME is disabled
That's it
Once I made these settings changes I ditched the dreaded "unable to verify..." message.
Try this and see how it goes.
BTW: I then re-tested with wifi and OTA data - both worked fine. And this worked with and without the latest ISO patch. The fact that I am Exchange 2010 might or might not be important.
Good luck.