I had the same issue. Select all contacts, export them to your desk top (so you have a copy, just in case). Then, go to settings and uncheck the box in iCloud that syncs your address book. It will wipe your computer address book clean. Afterwards, check the box again, and it will import all of the contacts from your iCloud (could take a few minutes to complete, depending on how many contacts you have). This solved my issue. All is in working order again. Hope this helps!