This is encouraging - I guess you are not using the same version of
slapd as I am? (I'm using 2.4.7, which apparently has a bug with
STARTTLS, at least in Debian it does).
I don't use Debian, and on production platforms I don't use the packages
supplied by the distro, but the rebuilds (which are available at
http://staff.telkomsa.net/packages/) of the Mandriva package, for which I am
the maintainer. The output in my reply was from my Mandriva 2008.0 x86_64,
running the 2.3.38 package supplied with the distro. I will try and test the
2.4.7 packages sometime later today.