So, I turn on debugging so I can see what OpenLDAP thinks is going on and I see that the krb principal is put as UID=PRINCIPAL. But no realm! OpenLDAP should do some realm mapping!