You should first test your configuration independently of Tridion. To do this, you need a simple LDAP client. (I recommend Microsoft LDP for this, as it uses the same Windows APIs that Tridion does to talk to the server. Most other simple LDAP clients are Java-based, and will therefore use the wrong certificate store.) Run the client on the Tridion server where you are experiencing difficulties.
Test that you can connect to the server on the specified URL and port. Check the logs on your LDAP server to verify that you can see the incoming connection. (What LDAP server are you using?)
Once you have verified that you can connect, attempt a bind using the DN and password of the "Search account" (as configured in the Tridion snap-in). If this succeeds, go on and verify that you can also bind as the user you are wishing to authenticate.
Throughout this process, continue to monitor the logs on the LDAP server to verify that you can see the expected events.
Having established that all your DNs and passwords are valid, double check that the Tridion configuration fully reflects the tested values. Restart all relevant processes. Test via Tridion.
If this process doesn't get you to an answer, you are ready to contact customer support at Tridion and the LDAP vendor to investigate issues with one or the other.