I had the exact problem people described below, same symptoms, same attempt to resolve, same results. (ie, Alfred WAS selected in System Prefs , Privacy, etc.)
Fixed it tho:
Exited Alfred
System Preferences
Security and Privacy
Privacy
Contacts
UNSELECTED / DE-CHECKED Alfred
Selected / Checked it again
Restarted Alfred
Problem resolved.
NOTE: The problem started after I installed a new mail client (Airmail), which had asked for and received access to contacts. Don't know if it's related, but seems like more than a coincidence that after I installed a new app that regularly hammers Contacts that another app lost access to contacts. #justsayin'