The answer turned out to be that the instructions given in the guide I was following did not produce a usable TLS certificate. I tested this by trying to use the generated certificate on other services (dovecot and postfix) which made them fail too.
I ended up using this guide, also from the official Ubuntu documentation to configure a self-signed CA (as suggested in the OpenLDAP documentation). The keys/certs this creates work perfectly and I'm even able to use the same cert/key for all of my TLS/SSL enabled services. Since this is for internal use, they are all self signed but gives me the option to make more easily.
The apparmor problem was very strange as well. I was getting a lot of errors to do with p11-kit and pkcs11. Doing some research I found that these seem to be tools ralted to certificates. I added the following lines to my /etc/apparmor.d/local/usr.sbin.slapd file.
Now the sldap server starts without a problem with TLS ready for use.
I hope this helps someone.