When using ldapsearch GSSAPI mechanism with a server whose reverse
doesn't match its DNS name, ldapsearch will do the DNS lookups and hand the
reverse DNS entry to GSSAPI. If the reverse DNS entry is not what is used by
kerberos then kerberos will fail.
Did you already try with -N?
$ ldapsearch -h
-N do not use reverse DNS to canonicalize SASL host name