When I've seen that error before and if I recall correctly it was one of the follwing issues:
1. The cert file (/etc/openldad/cacerts/) or where ever it's installed was not readable by the user that needed to read it. You could make it world readable for a test.
2. It's been a long time, but I think that this also may have caused the error. Not entirely sure though, notes are not available. We did not have the following in /etc/ldap.conf (RH5 system):
nss_base_passwd ou=. . . .
nss_base_shadow ou=. . . .
nss_base_group ou=. . . .