LDP SSL Port 636 Works - ldaps:// does not
Solution 1:
Your clients don't need their own certificate. They just need to trust the Certificate Authority certificate (or certificate chain) that signed the LDAP server's certificate. You didn't need to worry about this on the localhost because the CA certificate was already trusted by default.
It's not clear from your question whether the LDAP server is also the Certificate Authority and whether it is using the CA certificate as the LDAP certificate as well. Normally, these are two different certificates and the Certificate Authority lives on a different machine.
Some quick google'ing indicates there's an option you can set in the ldap.conf called TLS_CACERT or an equivalent environment variable called LDAPTLS_CACERT that you can point to a file containing any/all CA certificates in your environment (base64 encoded).
If you only have a single CA in your environment, you should be able to download a base64 encoded version of its public certificate. And if you can only find a DER encoded version, you can use openssl to convert it to base64.
openssl x509 -inform der -in cacert.crt -out cacert.pem