Your slow response times are probably due to a problem with your slapd configuration or a resource issue (heavy IO on the server or a networking problem).

What is loglevel set to in slapd.conf? A loglevel setting of anything other than 1 (the default) or zero has the potential to generate a lot of additional I/O. A setting of -1 can bring a loaded server to its knees because it logs all debug information and operation stats.

If loglevel is zero or one then the cause of the slow responses probably lies elsewhere. Setting the loglevel to -1 and running a few queries is the quickest way to learn if there are any problems with your slapd configuration (don't leave loglevel set to -1 any longer than required for troubleshooting if this is a production server).

Off the top of my head, a couple of things that can lead to slow reponses are: incorrectly configured backend, authentication mechanisms, network configuration or failure.

If logging reveals a problem on the server you should probably consult the OpenLDAP mailing lists, they're very helpful.

The settings for loglevel are documented in the slapd.conf man page.