Over the last few weeks my iPhone has been getting this terrible error with one of the Exchange 2003 sites that I administer. It was working fine, and then all the sudden, it stopped.
I took all the standard steps- re-added the account, deleted the sync partnership on the Exchange server.
Turns out that it was a little setting in the IIS 6 directory security tab.
IIS->(default/whatever you want website)->Exchange-> right click properties, tab up top ‘directory security’ -> ‘authentication…’ I needed to have integrated authentication checked.. and it wasn’t.
Checked it, restarted IIS.. and it worked.