Quick fix is to unlink the google account and relink it.
Problem : Everytime you try to sync, you get this error that says too many contacts deleted. My SIII running on Nexus 4 Jellybean rom kept giving me the error for a whole month , contacts and calender was not getting synced.
What causes it : If there is a big mismatch between your phone and google contacts, it causes this error. Sync finds too many mismatches and doesn’t know if it should copy from phone to Calender or calener to phone.
Resolution : In a nutshell, delete your google account from phone, delete contacts from phone and add it back on.
1. Make sure all your contacts are there on Google contacts. If you have contact on your phone that are not on google, take a note of such contacts. I didn’t have any local entries on phone not existing on google.
2. From Google : Export your google contacts ( just in case something goes wrong)
3. From Phone/PC : I used My phone explorer to delete all the contacts from the phone.
4. From Phone : Go to Settings >> Accounts > Google. Delete the existing account
5. From Phone : Go to settings >> Accounts > Add. Add your google account.
Wait for it to sync and that’s it . You should get all the contacts back and the sync should start working. Mine did.