As I Promised... an update.
After speaking with my Exchange administrator, he told me that the autodetect settings only works with Exchange 2007 and we have Exchange 2003. That's why the autodetect couldn't verify that certificate.
As mentioned previously, our certificate was from Godaddy, and we suspected that the certificate may not be on the iPhone (not being verisign and all). Apple actually has a page showing which certificates are installed on the iPhone, and the Godaddy was one of them, but we didn't trust them... why else would the certificate not be recognized. So I reinstalled the Godaddy certificate... The certificate was still not recognized. I don't know what an intermediate certificate or root certificate is, but we installed those too. At this point, I didn't delete the account and recreate it, but my inbox was still empty and no calendar info was synced.
At this point, we were wondering if the certificate was working at all. So I logged on to the OWA using iPhone's safari. It didn't recognize the certificate as from a trusted source, I told it to go ahead, and logged on. The OWA worked fine.
Just as a test, I did the same thing from Safari on my iMac. Same exact result. BUT... the second time you try to log on to OWA from iMac or iPhone, there was no more certificate error.
At this point we realized that the iPhone was not having a certificate problem. Still puzzled, we scoured the literature. Hmmm (try not to laugh) iPhone supports Exchange 2003 SP2. We had SP1. When we updated to SP2, I deleted the account and created a new one, and no more certificate error.
IMO, the only two things it could be is the install of the intermediate certificate (not likely) or the update to SP2 (likely)
SO LISTEN UP, MAKE SURE YOUR EXCHANGE SERVER IS AT LEAST THE VERSION APPLE SUPPORTS!!!!
But... There is still a problem, maybe Ycore can help me.
No matter what I do, I still have an empty Inbox and the calendar info is not syncing. Does anyone have an idea how to fix that?