It is strange.
Which Linux distribution are you using?
What kind of LDAP server is it? OpenLDAP or a commercial one?
Is that a TLS or plain connection?
LSWS use OpenLDAP's client library to contact LDAP server, and that's the error message reported by the library.
If you have not done so, you can try to do a search with OpenLDAP's command line client "ldapsearch" with the same information in your LDAP url, see if it works.
Also you can use command "tcpdump my.host.name" to trace tcp activities between two machines, please let me know what you get.