I recently had to acquire a new CA cert for my Exchange 2007 server for OWA and Outlook Anywhere (RPC over HTTPS). Since then, all Iphone access to Exchange accounts has broken. I have tried deleting the email account on the iphone, rebooting and reconfiguring accounts (thinking it needed to clear some cache related to the certificate). On entering the new account, Iget"Exchange account verification failed"
Is your new certificate by any chance a wildcard cert? I.E. *.domain.com ? I don't believe the iPhone supports them.