I've had the some problem for about a week now, and it has been very
frustrating, but I finally figured what was wrong. Somehow in IIS the
exchange virtual Directory that is used for ActiveSync had the
"enable anonymous access" check box checked. That caused problems
when new users tried to sync with ActiveSync.

1. Open IIS
2. Right Click on Exchange or ExchDAV (KB817379)
3. Click on Directory Security
4. Under Authentication and access control click on edit
5. Uncheck "Enable anonymous access"
6. Click ok, and then restart IIS.