In the recent conversion to iCloud I ended up with a few hundred spare contacts on the trusty iPhone. Those who have tried the old fashion method of correcting this problem know how much fun it is to go into each of several contacts and delete them. WIth hundreds the fun grows into outright pain.
If you have an Exchange account setup on your phone that you're not using there is a quick fix. Go into Settings > Mail, Contacts and Calendar > and then to your exchange account. Set the Exchange account to sync contacts and you'll be prompted to delete local contacts. Once it does the work for you then turn contact sync back off and you're good to go.
What isn't clear is that this won't delete your contacts syncing with other accounts. It only deletes those contacts that are local to just your phone. This also only seems to work with Exchange accounts.
Another long time frustration with Mobile Me and now iCloud and address book sync has been what to do with those old addresses.