The most probable reason is Security settings on user account in Active Directory.
Check Application Section in the Event Viewer of a new Exchange Server.
Search for warnings with the following details:
Source: MSExchange ActiveSync
Event ID: 1008
Description: An exception occurred and was handled by Exchange ActiveSync. This may have been caused by an outdated or corrupted Exchange ActiveSync device partnership. This can occur if a user tries to modify the same item from multiple computers. If this is the case, Exchange ActiveSync will re-create the partnership with the device. Items will be updated at the next synchronization.
Although Microsoft suggests to wait for the partnership to be updated automatically (http://technet.microsoft.com/en-us/library/ff981815(v=exchg.141).aspx). You can proceed to next steps to see if the problem is in security configuration of the user account.
- Open Active Directory Users and Computers. Find the affected user account and open Properties of the user.
- In the User Properties window, navigate to Security tab and click on Advanced (To view Security tab you need to enable Advanced Features in Active Directory: View >>> check Advanced Features)
3. In the Advanced Security Settings window click on Enable Inheritance. If it is already enabled (when there is only Disable Inheritance button), click on Restore Defaults.
Check if Inheritance is enabled in the Security settings for other users.