In release 5.0.15 i'm not experiencing the problem, in 5.0.13 I solved using a different LDAP filter than the one proposed by zimbra.
using zmprov gacf zimbraGalLdapFilterDef you can see the definition for adAutoComplete that you can edit, otherwise try to use ldap instead of active directory and put (|(cn=%s*)(sn=%s*)(givenName=%s*)(mail=%s*))
as filter. |