A segunda linha do seu log diz que o slapd não pode se ligar a um de seus soquetes:
slapd[9417]: daemon: bind(9) failed errno=13 (Permission denied)
E a última linha mostra que o problema é causado pelo AppArmor:
kernel: [62956.076553] type=1400 audit(1393066360.532:44): apparmor="DENIED" operation="mknod" parent=9404 profile="/usr/sbin/slapd" name="/run/slapd/ldapi" pid=9417 comm="slapd" requested_mask="c" denied_mask="c" fsuid=0 ouid=0
Portanto, isso precisa ser corrigido na política do AppArmor para o slapd, seja pelo Ubuntu ou manualmente.
(e não tenho ideia de onde você tirou todo o certificado TLS)