Can you reset the sync history in iTunes/Settings/Devices?
You may also try this, copied from: Sync Services: Advanced troubleshooting for contact and calendar syncing
- If you see the Sync menu in the menu bar, skip to step 4:
- If you do not see the Sync menu in your menu bar and you are not a MobileMe member, skip to step 8.
- If you do not see the Sync menu in your menu bar and you are a MobileMe member, you will need to enable Sync status in System Preferences. Follow these four steps to enable the Sync menu and then proceed with the subsequent troubleshooting steps as necessary:
- From the Apple () menu, choose System Preferences.
- From the View menu, choose MobileMe.
- Click the Sync tab.
- Select the option "Show Sync status in menu bar."
- Hold the Option key on your keyboard, then click the Sync menu in the menu bar:
if you see the Sync menu but you are unable to open it, skip to step 8.
- Choose Reset Sync Services.
- Click Reset Sync History.
- Test for the original issue. If the issue persists, or if you are unable to open the Sync menu, follow these steps:
- In the Finder, choose Utilities from the Go menu.
- Open Terminal.
- In the Terminal window, type or paste the following command on a single line:
/System/Library/Frameworks/SyncServices.framework/Versions/A/Resources/resetsync .pl full
- Press Return.
- When the operation is complete, quit Terminal.
Are you using Mobile Me or iCloud? MobileMe was shut down a bit ago and iCloud should have solved thses issues for you. Did they?
One way to easily force a resync of all of your devices to the Contacts/Address book database that is in the cloud is to enter a new test address using each device. I call thenm iPad. iPhone and iMac, entering each from the respective dvice. They shoudl each appear instantly on all the other devices. If they do not, you can easily tell which one's iCloud sync is misbehaving.
BEFORE PROCEEDING, BACK UP THE MISBEHAVING DEVICE'S CONTENTS!
Go the iCloud settings for that device, use the sign out button. The warnings you will see are scary but harmless. However, you push these buttons at your own risk.
Wait a few minutes, sign back in top iCloud using your Apple ID and password. This forces a reload of the contacts database form the iCloud storage and all of your devices should now display the same contacts database.
This has worked for me on two separate accounts, mine and a coworker's. Doesn't mean it will work for you. Doesn't mean you know what you're doing or that it is a harmless suggestion.