A resposta acabou por ser que as instruções dadas no guia que eu estava seguindo não produziram um certificado TLS utilizável. Eu testei isso tentando usar o certificado gerado em outros serviços (dovecot e postfix), o que os fez falhar também.
Acabei usando este guia , também da documentação oficial do Ubuntu para configurar uma CA auto-assinada (conforme sugerido na documentação do OpenLDAP). As chaves / certs que isso cria funcionam perfeitamente e eu posso até mesmo usar o mesmo certificado / chave para todos os meus serviços habilitados para TLS / SSL. Como isso é para uso interno, todos são auto-assinados, mas me dá a opção de fazer mais facilmente.
O problema apparmor foi muito estranho também. Eu estava recebendo muitos erros para fazer com p11-kit e pkcs11. Fazendo algumas pesquisas, descobri que essas ferramentas parecem ser usadas como certificados. Eu adicionei as seguintes linhas ao meu arquivo /etc/apparmor.d/local/usr.sbin.slapd.
/usr/share/p11-kit/modules/ r,
/usr/share/p11-kit/modules/* r,
/usr/lib/x86_64-linux-gnu/pkcs11/ m,
/usr/lib/x86_64-linux-gnu/pkcs11/* m,
Agora, o servidor sldap é iniciado sem problemas com o TLS pronto para uso.
Espero que isso ajude alguém.