I am still having this problem. It is very interesting though what I have found out. I have around 6400 contacts. I can set my Mac to sync either via iCloud or google. My preference is to sync with iCloud to keep the groups syncing to my iOS devices. Google groups don't sync. Here's the interesting info..
If I sync my computer's contacts with google, Alfred works fine. If I sync with iCloud, Alfred can take as long as 30 seconds to find a contact. With google it is instant.
There is definitely a bug with Alfred and contacts syncing with iCloud. May have to go back to Launch-bar, Alfred is better, but I look up contacts more than any other single task.