The first thing we need to ensure is that Wireless Sync is enabled for contacts. To check this setting this follow these steps:
1. Open Address Book
2. Press the menu button and select Options
3. From Options ensure "Wireless Sync" is set to Yes
4. Exit and Save
If this option is already set to Yes please change it to No and Exit and Save. Once you save the setting wait 30 seconds and then change it back to Yes.
If you could please post back with your results it would be appreciated.