Synchronising WM5/ WM6 to a SP1 Server 2003 running Exchange server 2003 SP2 you receive one of the above error messages or one of the following:
"Your Microsoft Exchange server does not have permission to synchronise with your current settings. Contact you exchange administrator "
You are most likely to see this message if the following Conditions are true:
* The Exchange virtual directory on an Exchange back-end server is configured to require SSL.
* Forms-based authentication is enabled.
The following Article helped me resolve this issue, simply re-create the Exchange virtual container without SSL limited to only access from the system itself and then one short registry change later you will find it works.
See link: http://support.microsoft.com/kb/817379