Very stuck, very pissed, very much in need of some help from an Exchange expert or someone who knows a lot about MS ActiveSync 4.1 and Cingular 8125 PDA.
So here's the problem. I install the MS ActiveSync 4.1 on the PC and go to sync up the PDA with the Exchange server and I get the following error:
"Your account in microsoft exchange server does not have the permission to synchronize with your current settings. Contact your exchange server administrator
Support code:85010004"
Which is utter rubbish. This happens on any account I try, even the Domain Admin account

I have done the following:

Followed
THIS KB inside and out and the solution does not fix my problem.

Reinstalled the certificate of the PC the PDA is syncing to onto the PDA.

Fooled around with the Exchange permissions through and through for the user's mailbox.

Went to the Exchange System manager and configured the Mobile Services under Global Setting properties to not require Device Security

Made absolutely sure that SSL was not required
The Exchange server specs:
MS Windows Server 2003 SP1
MS Exchange Server 2003 SP2
WSUS runs on this server also.
I would be so thankful if someone has any idea that I could possibly try. Just by intuition it seems to me to be a certificate problem. I must admit that I am still a noob when it comes to Certificate Authority and am still learning it. I guess I could be exporting the wrong certificate to install on the PDA, but there is virtually not much documentation on this that I can find.
One last thing. There are some Technet webcasts that go over ActiveSync issues that I have not watched yet, so perhaps the answer lies there, but I am too busy to watch them

Thanks in advance.