Thanks for your additional information. I think we have a good understanding of how this bug happens in the case where kdc.conf and krb5.conf have conflicting realm information or where kdc.conf does not supply the realm that the KDC is actually serving. My recommendation is that we look into ways to change the software so the database ends up in the right place if the config files conflict. It's likely you'll get other bad side effects, but this seems particularly problematic.
--Sam