What filter are you using? What LDAP directory are you connecting to? When you're running your search, how close, physically, are you to the directory server and how fast is your connection? Have you checked latency/ping times?
There can be any number of reasons why you will experience slow connections to services over the network. Pinpointing where the slow down happens is critical. Check your network connection, try querying from another host (physically close to the LDAP directory, or on your same network), using ldapsearch or other query tools (like Apache Directory Studio even), and making sure that the attributes you are querying for are indexed in the directory for fast lookup.
And as Jerry mentioned, once you've narrowed it down to the client library, you can hook into the internal events to see what's happening and where it's going slow. Try setting up basic logging with the instrumentation hooks.