Quoting Christian Guenther <chris@blaue-elise.net>:
> and set up my /etc/init.d/ldap start-script accordingly
You did start the server with the flag(s)
-H "ldap:/// ldaps:///"
Don't forget the " characters...
> ldapsearch -H ldaps://talamus.blaue-elise.net/ -x -b "" -s base
Did you enter 'talamus.blaue-elise.net' as the hostname when you
created the certificate?