This has been tricky, but not wanting cleartext passwords to go over the wire I figured it out. Mac OS X, as of version 10.5 (Leopard), the clients have been very picky about using LDAP over SSL. If anything is 'wrong' (even though it may not be considered as such by unsuspecting system administrators), the process will fail silently. I've tested this on Snow Leopard (10.6.2) and Leopard Server (10.5) with OpenLDAP.
First, you must use SSL, not TLS with starttls. This means running your LDAP server on port 636 (by default). In OpenLDAP this is achieved by using the -h option to start it, telling it "-h 'ldap:// ldaps://'", for instance. So far this is 'normal', after all not all clients always support TLS.
From here on it gets specific.
Second, the certificate must not be self-signed. It must be signed by a CA (but it can be your own CA if you want). As of Snow Leopard, the CA's certificate must be in the System keychain, or in the System Roots. This means a CA recognised by the OS will work out-of-the-box. In Leopard this is different, as the keychain and OpenSSL don't know about eachother. In this case you must configure the certificate in /etc/openldap/ldap.conf instead.
Third, the reverse DNS must match. This is not normal procedure: normally the certificate is checked according only to the host name you enter (i.e., forward DNS). Again if this is off, it will fail silently. Interestingly, the system will accept simply putting the host in /etc/hosts if this works for you.
I have tried countless variations of this scenario. The only thing that I found would work is what is described above.