This is so random.. I never had an issue with this until I added this last batch of contacts.

Whenever I go into the Address Book, and start to type in the first few letters of a contacts name, it says "No Addresses" for a few of the contacts. One of those, for example, would be my own entry in the addressbook.

Some work, some don't. This is crazy!!!

Any idea what is causing this?

i have the same problem .... did you figure out how to solve it ? thanks

Do you have a Filter on? Go into the Address Book, click the wheel and click Filter. Uncheck any boxes that are checked.