A co-worker who had problems with a different box trying to authenticate via this AD server also pointed out to me that the new certifcate from the AD server does not have the fully-qualified domain name in it.
I used the x509 command to get info on the certficates. On the old one I see: Subject: CN=chaent3b.main.foo.com [name has been changed] On the new one I see: Subject: DC=com, DC=foo, DC=main, OU=Domain Controllers, CN=CHAENT3B
This is your problem. Whoever made your cert did it wrong. The CN field should be the fully qualified domain name of your server; if they don't match, SSL doesn't work properly (this is to avoid man in the middle attacks).
Since the certificate is worthless for avoiding man in the middle attacks, you might as well tell openldap to not check for valid certificates. I guess at least your connection will be encrypted. Set the following in /etc/openldap/ldap.conf:
TLS_REQCERT never
In all reality, your AD admin should re-request the certificate, and do it properly...
V/r,
Ryan Lane