I suspect many people's iOS Contacts have been trashed by iCloud, but only a small percentage realize how bad things are. It may explain some of the mysterious data use and battery life problems some see.
I can't prove this of course; I'm not about to study a random sample of 100 devices. I can only go by my own disastrous experience and Emily's recent malfunction.
In my case the bug had to do with a change between MobileMe and iCloud in the handling of line endings resulting in large numbers of 'Groups' metastasizing between my devices. It was very hard to diagnose and fix that bug; since then things have seemed to go well with my use.
Emily's malfunctions seemed simple at first. I noticed she had both addresses on her device and in iCloud. I didn't expect that, but I figured it would be easy to clean up. . Then I discovered about 3,500 entries in Contacts that showed up only as 'No Name'. This isn't a new problem and I don't know how long Emily had it. She never noticed, I suspect most non-geeks ignore that sort of thing. I wonder if it explains some battery life issues she's had, and even Spotlight and disk access issues on some of our older machines as these malformed entries propagated. (As noted below, during the removal process the OS X Contacts app used 25 GB of virtual memory and locked up my 27" iMac.)
Removing these malformed null-value entries was much harder than expected. Something about processing the deletes using Mountain Lion Contacts.app consumed vast amounts of virtual memory -- almost completely paralyzing my 2 yo iMac with the usual Spinning Beach Ball of Death (SPOD, SBOD, spinning wait cursor). (See: Getting control of a Mac when rogue software consumes virtual memory.)
In retrospect I think I wonder if I should have disabled my network connection, made the changes, and then reconnected and let iCloud process the cached change list. In any event, this is more or less what I did to delete them; in our home we have 1 iOS device (Emily iPhone) and two OS X devices (Mountain Lion Contacts.app and older Lion-only machine running Address Book.app) that synchronize to her iCloud account.
- Work from our primary Mountain Lion machine, and create a local backup using the Contacts Archive function.
- Turn off iCloud synchronization from the other iOS and OS X devices and delete all local contacts. On iOS the OS will offer the delete option, on OS X you have to delete them manually. (With iCloud sync off delete is easy.)
- Open Safari to view changes there.
- Because of the problems I ran into I suggest turning off Time Machine and, if you know how to do it, disable Spotlight disk indexing. At least uncheck Contacts from the Spotlight Search Results in the Pref Pane. You'll add them back in after you are done.
- Close all other apps and log out all other users.
- Do this incrementally - delete a few hundred, then quit and restart Contacts. When I skipped some of the above steps and tried to delete all 3,500 at once my machine locked me out. After some geek gymnastics I found Contacts.app was using 25GB of Virtual Memory -- enough to store about 1,000,000 contacts. Very little CPU was being used, but that much VM use is fatal.
- When you're done run Contacts Cleaner if you own it.
- Restart OS X, reenable Time Machine, Spotlight, etc.
- On iOS (iPhone for example) reenable iCloud account. (In Emily's case this brought up the merge with local dialog -- the original small problem. See  for the easy fix for that, it does mean letting changes sync back to desktop as well).
- Once that's settled down, reenable iCloud accounts on other devices. Let Spotlight catch up indexing them. You can disable then reenable Contacts search if you like
 If that's your only problem here's the way to clean it up:
- Remove iCloud account from phone (you'll put it back).
- Make sure only local device Contact remain.
- Add iCloud back -- you'll get offer to merge them. Merge.
- Clean up duplicates, easiest to do that on a desktop account using Contacts Cleaner (with my latest version I didn't disable network connectivity when doing this) or the dangerous fully automatic built-in Mac desktop duplicate remove.
- iCloud transition went as expected - disastrously 6/2012
- iCloud group replication resolved by AppleScript 7/2012
- An AppleScript to prevent the iCloud CRLF bug - normalize line endings 7/2012
- Synchronization is Hell 10/2008. Technologists underestimate this problem so commonly it has to be a universal wetware malfunction.
- Spanning Sync contacts cleaner - a quick review 1/11 (it's been upgraded since then, seems even better)
- Gordon's Tech: Getting control of a Mac when rogue software consumes virtual memory 1/12/2013
More on the No Name bug: