I was having the same problem and discovered that by default I was searching Google contacts, the sim and the phone. Within Google contacts however I was not searching ungrouped contacts. When I fixed it everything worked.
To see what you are searching:
- go to contacts right next to people at the top of the window (to the left of the +) and push the pull down {note that This brings up the list of places you are looking when you search for contacts}
- now push the pull down next to Google {this brings up the list of places I am searching within Google contacts}
).
What I discovered is that the default was too look at all of the grouped contacts but not "(ungrouped contacts)" which was deselected.
I simply checked "(ungrouped contacts)" and it finds everyone now!
— modified on Mar 7, 2012, 6:05:04 AM