Contact sync problems, Contacts Cleaner and The Nuclear Option
There are two kinds of people in the world: those who have no problems with iCloud sync, and people who use iCloud sync. Well, OK, maybe that's an exaggeration, but I have had plenty of problems with iCloud sync well back into the MobileMe days.
Most of the problems relate to syncing contact data. For some reason, iCloud periodically stops working in some non-obvious way. The way I usually discover this is when I realize that some device does not have some piece of information which was either added or changed on another device.
Having dealt with this problem for several years, I am now accustomed to performing "The Nuclear Option" when it comes to fixing my contact database. The Nuclear Option is a backup of my contacts from every single device and from the iCloud web client, followed by a complete purge, reimportation and de-duplication pass. I cannot guarantee that it will work for you, but it has worked for me.
Apple's Address Book / Contacts app creates backup files in its own format, but I prefer to export my contacts in the industry-standard vCard format to purge them of any lingering iCloud metadata.
To export all of your contacts as a single vCard archive, you need to select them all before choosing File » Export » Export vCard... -- otherwise you will only export the currently selected contact. vCard exports should be very "portable"; you should be able to use them for importing into Google or other places if needed.
On iCloud.com, the export menu item is found under the small gear icon at the lower-left corner of the page. Select all your contacts (you can use the Command-A shortcut for this purpose), then Export vCard.
Please note: If you need to preserve group information, be sure to use the Contacts app's native format instead of vCard; export as "Contacts Archive..." instead.
My step-by-step process does not preserve group information. I only use Smart Groups which I can easily recreate, so this is not an issue for me, but if you have extensive groups, this may not work for you. Here's the rundown:
Export contacts from each Mac, iOS device and iCloud.com.
Verify each export. (Tip: if you use QuickLook on a vCard file, it will show you how many contacts are in it.)
Move of all those exported contacts somewhere really, really safe.
Delete all contacts from iCloud.com. (Seriously, you verified those exports before, right?)
Sync each device and make sure each Mac and iOS device has zero contacts.
Disconnect your iMac from the network (unplug the Ethernet adapter and turn off Wi-Fi).
Import all of the contact information gathered in step 1. (This won't produce as many duplicates as you'd expect.)
Run Contacts Cleaner until it fixes all problems (which may require running the app several times).
Export a copy of the cleaned-up data for safe-keeping.
Look through all contacts to spot any obvious problems.
Export all contacts from Contacts.app to a vCard named something like "All-Contacts–2012–02–18.vcf" and keep it somewhere safe.
Re-connect iMac to the network and let it sync back to iCloud and related devices.
I have only two complaints, both of them relatively minor. The first is that the app gets confused by SMS "short codes" and a few non-USA phone numbers that I have in my address book. It's easy enough to ignore them, but after a while it would be nice to be able to say "No, really, this number is OK, forever." Secondly, iCloud managed to replicate the "Spouse" field in my vCard about 100 times and Contacts Cleaner doesn't look for duplicate data in those fields. It would be nice to be able to turn on some sort of a "deep-cleaning" mode which would tell Contacts Cleaner to search all fields for duplicate data.
If you have sync problems with your contacts, try these steps.