The issue relies in the "external GAL", I've seen it elsewhere yesterday.
Here for example, someone with the same problem (with Zimbra 4.5.3) :
gal search issue
Lionel, what external GAL are you using (LDAP, AD, stg else) ?
What are the search/filter parameters you've used while setting up the external GAL ?