I encountered a problem synchronizing the contacts on my new Android phone recently and found that others have encountered similar problems but have not found any solutions on internet. I finally solved the problem and am sharing it here.
The main cause in my case was the Google Device Policy App.
To avoid the problem be sure to successfully synchronize all your Google accounts before activating the Google Device Policy app.
If you activated the Google Device Policy app before you successfully complete the synchronization of all your Google Accounts, you may find that the contacts synchronization will not work.
To fix it:
Force stop the Google Device Policy App (to do that go to Settings -> Applications -> Manage Applications -> (find Device Policy) ->
Then go to Accounts & sync to synchronize all your Google accounts.
Once done, you can reactivate your Device Policy App by finding the app under All apps and click on it activate it against your corporate account.
I found another contributing factor to the synchronization has to do with illegal characters in your contact information. If you have ' in your contact name, it will also cause all the synchronization to stop. The only way to fix is to remove the illegal characters and then reset the device back to factory config and then set it up again.
However, before you do that, try rebooting your device first. This may sometimes fix the problem so you don't have to go through the hassle of reconfiguring everything. I have tried rooting and backing up using Titanium backup but it did not allow me to restore everything.