SOLVED: "TLS init def ctx failed" -1 (Ubuntu)

# Disable AppArmor temporarily! - this helped me!
/etc/init.d/apparmor teardown

# Assuming you've already set appropriate rights on the file TLSCertificateKeyFile and others as mentioned http://blog.rot13.org/2016/01/debian-openldap-with-gnutls-and-openssl-certificates.html

# Start OpenLDAP again
service slapd start

# Or debug it with (for those who prefer storing config in the plain text file, rather than in LDAP)

/usr/sbin/slapd -g openldap -u openldap -f /etc/ldap/slapd.conf -d -1