In order to get LDAP etc. using SSL from the get go you need to make sure the LDAP client has the CA certificate that was used to issue the certificate to the LDAP server.
Grab the CA certificate in PEM format and copy it into the /etc/ssl/certs folder. Then merge it into the ca-certificates.crt file. And for good measure copy in the certificate from the host too.