If you haven't done so already, you should verify that:
s_client -> s_server
works, then if
s_client -> slapd(8)
works. In both cases, be sure to use appropriate s_client
flags to enable server certificate verification. (If you
have questions about how to use s_client or s_server, see
the OpenSSL docs, use OpenSSL support lists.) And then,
if you still have problems, I suggest you enable both client
and server side debugging, rerun your simple authentication
(or just anonymous) bind, and then examine the output for hints.
And you might try 2.2.13 as, IIRC, some of ldapsearch(1)'s
error reporting was improved (though I don't recall if it
would make a difference here).