Comment 3 for bug 1363897

Edit /etc/krb5.conf, and change the section:

[dbdefaults]
        ldap_kerberos_container_dn = dc=example,dc=com

to

[dbdefaults]
        ldap_kerberos_container_dn = cn=krbContainer,dc=example,dc=com

This issue appears to have been introduced in kdb5_ldap_util 1.12:
http://mailman.mit.edu/pipermail/kerberos/2014-March/019575.html

Basically, you have to start ldap_kerberos_container_dn with a 'cn'.

Unfortunately, I believe the official Ubuntu LTS documentation is to blame here.
Anyone following those directions is going to run into this issue:
https://help.ubuntu.com/14.04/serverguide/kerberos-ldap.html#kerberos-ldap-primary-kdc