If you can do ldapsearch -x okay but ldapsearch gives a
Permission denied in replay cache code error,
when running slapd under openldap user but auths okay when ran as root (check klist for ldap/server.example.com ticket)
Then see if the following works from the console. If it does then integrate it into /etc/default/slapd otherwise you may try KRB5RCACHETYPE=none as a further workaround (though having a replay cache is preferred)
env KRB5_KTNAME="FILE:/etc/ldap/ldap.keytab" KRB5RCACHEDIR=/var/local/lib/ldap slapd -u openldap -g openldap -d 255 -h "ldap:/// ldapi:///"