Could use Time Machine
If you haven't added or deleted any contacts recently, or you are not too worried about possibly losing some you have added and having to delete some you already have, before you follow these steps you could restore your address book from Time Machine, going as far back as you are comfortable with.
i had this problem with a new iphone 4. i tried everything that people on multiple forums recommended and nothing worked.
if you have a new iphone and your contacts and not coming from an old model i think i have found the problem. it appears that the contacts file is corrupted because one contact has a problem. all of your contacts are grouped together in one "file" so if one contact is corrupted, the entire file will be too and will not sync.
to fix it (this is very manual) you should:
1. create a new group
2. move contacts to that group in batches (try 10 or alphabeitical)
3. sync the new contacts group ONLY
4. if that works, add 10 more contacts
5. repeat this until the error message appears; you will know which batch has a corrupted contact
6. find the corrupted contact within that batch by trial and error and delete it from the contacts list and the new group
7. add the remainder of the contacts in batches until the full group syncs
8. after this is completed you can delete the group, re-create the deleted contact(s) in the main contact list and all contacts should sync normally.
i did this and it worked. good luck
If you haven't added or deleted any contacts recently, or you are not too worried about possibly losing some you have added and having to delete some you already have, before you follow these steps you could restore your address book from Time Machine, going as far back as you are comfortable with.