This bug is unresolved by localization-config 1.0~rc1 as noted in the bug history. The underlying issue has been resolved in heimdal 0.8.x HEAD, and relates to adding krb5EncryptionType attributes to the LDAP entry at inappropriate times (they should only ever be updated, not added).
Attached is a backport of the patch. It is pretty trivial. Also, a related question... is there a possibility of adding a debconf question to ask if LDAP is going to be used as a back end? If so, then we shouldn't be running 'kadmin -l init $REALM', as LDAP needs to be configured and working first. That could lead to a whole bag of other questions, but starting with " Is it LDAP? Leave it to the user" seems like a good start. Once I learn how to use debconf, I might tackle it (as it relates to a project I am working on), but I'm not there yet.
hdb-ldap-enctypes-fix.dpatch
Description: application/shellscript