Apparently Debian decided to build libldap with GnuTLS instead of OpenSSL in Debian lenny, which can cause a lot of problems connecting to ldaps servers. Rebuilding the library with OpenSSL instead of GnuTLS fixed the problems for me.
Building the library by yourself is quite simple:
$ apt-get install dpkg-dev build-essential fakeroot debhelper libdb4.2-dev libgcrypt-dev unixodbc-dev libncurses5-dev libperl-dev libsasl2-dev libslp-dev libltdl3-dev libwrap0-dev debconf-utils po-debconf quilt autotools-dev libtool automake autoconf time libgnutls-dev libssl-dev
$ apt-get source libldap-2.4-2
$ cd openldap-2.4.11/
edit debian/configure-options to use OpenSSL instead of GnuTLS and then run the build. Make sure your loopback interface is configured and up and you have defined localhost in your /etc/hosts as the testsuite will fail othwerwise.
$ dpkg-buildpackage -rfakeroot -uc -us
You then should have a deb package with libldap build against OpenSSL.
If you do not want to rebuild libldap by yourself, feel free to use mine: