Rebuilding Address Book metadata
Thanks rpontremoli, this did it for me, too. Unfortunately the Alfred support page had been deleted, but google cache still remembered the instructions. For future reference, here they are:
It's easy to completely reset the Address Book.app metadata by following these steps:
1. Back up your Address Book: File > Export > Address Book Archive (or Contacts archive in Mountain Lion)
2. Quit Address Book.app or Contacts.app
3. Delete the following folder in your home folder:
~/Library/Application Support/AddressBook/Metadata/
If you use iCloud, delete the following folder in your home folder:
~/Library/Application Support/Address Book/Sources/RANDOMNUMBERS/Metadata/
Then, ensuring you have backed up your contacts, go to the iCloud System Preferences Pane and uncheck the box for Contacts. When shown options, choose Delete from Mac. Once deleted, recheck the box and your Contacts will re-sync.
4. Restart Address Book.app and wait a few moments, this folder will be recreated and repopulated
5. Wait a minute or so for OS X to reindex this folder
I'm having the same issue and it doesn't have anything to do with the privacy tab.
It seems that the Address Book metadata is corrupted. There's has a simple fix explained here:
http://support.alfredapp.com/kb:rebuild-address-book
The problem is that, at least in my case, the metadata corrupts over and over again. I'm afraid this may be an issue for iCloud users on 10.8 But I still cannot find anybody posting a solution to this.