I had issues trying to connect to our Exchange also, but then I found a fix. I don't remember if this was the same issue or not..... Go to Settings --> Region & Language, change to US English (Mine was already setup to US English) just reselect it, apply and restart the phone. Mine worked after restart. Hope this helps.
Here is a link to a similar problem with the cert
How to install a security certificate on my Windows 7 phone for - Microsoft Answers
I know that using mail.server.com should work, have you tried using Outlook Web Access link ?