I get that error when I try to connect to our exchange server. I've seen other answers to this for the 6.5 platform that say something like "ADUC right-click properties -> Security Tab -> Advanced -> check inheritable and user must not be a domain admin".... Okay, well I'm a domain admin, so what must I do to have a working phone?
FYI: I'm using the Samsung Focus. We have plenty of other mobile devices that use Active Sync everyday with no problems (iPhone, Black Berry, WM 6.5 and probably a Palm or two).