Kerberos KDC won't start : invalid credentials

I'm having troubles my kerberos server (LDAP back-end). I wanted to restart the KDC service and it failed. It has been working fine for several weeks.

Since I had just tweaked LDAP ACLs, I tried the following commands:

$ slapacl -D cn=kdc-srv,ou=krb5,dc=example,dc=org -b ou=krb5,dc=example,dc=org entry/read
authcDN: "cn=kdc-srv,ou=krb5,dc=example,dc=org"
read access to entry: ALLOWED

-

$ ldapsearch -b ou=krb5,dc=example,dc=org -D 'cn=kdc-srv,ou=krb5,dc=example,dc=org' -W
Enter LDAP Password: 
ldap_bind: Invalid credentials (49)

-

The result of the second command doesn't make any sense to me. How can it be allowed and still fail?

EDIT: Also if I do this instead:

ldapsearch -Y EXTERNAL -H ldapi:// -b ou=krb5,dc=example,dc=org -D 'cn=kdc-srv,ou=krb5,dc=example,dc=org' -W

I get No such object (32).

-

I first compared the password of the KDC DN in the LDAP directory with the one stashed in /etc/krb5kdc/service.keyfile and they are the same.

Here are the logs when trying to restart the KDC:

systemd: Starting Kerberos 5 Key Distribution Center...
-- Subject: Unit krb5-kdc.service has begun start-up
-- Defined-By: systemd
-- Support: https://www.debian.org/support
-- 
-- Unit krb5-kdc.service has begun starting up.
krb5kdc: Couldn't open log file /var/log/krb5/kdc.log: Read-only file system
slapd: conn=1055 fd=14 ACCEPT from PATH=/var/run/slapd/ldapi (PATH=/var/run/slapd/ldapi)
slapd: conn=1055 op=0 BIND dn="" method=128
slapd: conn=1055 op=0 RESULT tag=97 err=0 text=
slapd: conn=1055 op=1 SRCH base="" scope=0 deref=0 filter="(objectClass=*)"
slapd: conn=1055 op=1 SRCH attr=supportedFeatures
slapd: conn=1055 op=1 SEARCH RESULT tag=101 err=0 nentries=1 text=
slapd: conn=1055 op=2 UNBIND
slapd: conn=1055 fd=14 closed
slapd: conn=1056 fd=14 ACCEPT from PATH=/var/run/slapd/ldapi (PATH=/var/run/slapd/ldapi)
slapd: conn=1056 op=0 BIND dn="cn=kdc-srv,ou=krb5,dc=example,dc=org" method=128
slapd: conn=1056 op=0 RESULT tag=97 err=49 text=
krb5kdc: Cannot bind to LDAP server 'ldapi://' as 'cn=kdc-srv,ou=krb5,dc=example,dc=org': Invalid credentials - while initializing database for realm EXAMPLE.ORG
krb5kdc: krb5kdc: cannot initialize realm EXAMPLE.ORG - see log file for details
systemd: krb5-kdc.service: Control process exited, code=exited status=1
systemd: Failed to start Kerberos 5 Key Distribution Center.
-- Subject: Unit krb5-kdc.service has failed
-- Defined-By: systemd
-- Support: https://www.debian.org/support
-- 
-- Unit krb5-kdc.service has failed.
-- 
-- The result is failed.
systemd]: krb5-kdc.service: Unit entered failed state.
systemd: krb5-kdc.service: Failed with result 'exit-code'.
slapd: conn=1056 fd=14 closed (connection lost)

-

And here are the LDAP ACLs:

olcAccess: {0}to dn.subtree="ou=krb5,dc=example,dc=org"
  by dn.exact="cn=adm-srv,ou=krb5,dc=example,dc=org" write
  by dn.exact="cn=kdc-srv,ou=krb5,dc=example,dc=org" read
  by * none
olcAccess: {1}to attrs=userPassword,shadowLastChange
  by dn.exact="cn=other,dc=example,dc=org" write
  by anonymous auth
  by * none
olcAccess: {2}to dn.subtree="ou=people,dc=example,dc=org"
  by dn.exact="cn=other,dc=example,dc=org" write
  ...
  by * none
...
olcAccess: {6}to dn.subtree="ou=systems,dc=example,dc=org"
  by dn.exact="cn=other,dc=example,dc=org" write
  ...
  by * none
olcAccess: {7}to dn.base=""
  by * read
olcAccess: {8}to *
  by dn.exact="cn=other,dc=example,dc= org" write
  by users search
  by * none

Any ideas?