ldap client crypto question

I'm using a custom perl script, using perl-ldap (Net::LDAP).

I'm trying to connect to my server via ldaps://.  On RHEL4 (and  
CentOS4) this works without problem.  On RHEL5, I keep getting  
"stronger confidentiality required" error messages.

Connecting from an RHEL4 client gives me:

Aug 15 16:51:52 csenet slapd2.3[4105]: conn=1318 fd=15 TLS established  
tls_ssf=256 ssf=256
Aug 15 16:51:54 csenet slapd2.3[4105]: conn=1318 op=0 BIND  
dn="<binddn>" method=128
Aug 15 16:51:54 csenet slapd2.3[4105]: conn=1318 op=0 BIND  
dn="<binddn>" mech=SIMPLE ssf=0
Aug 15 16:51:54 csenet slapd2.3[4105]: conn=1318 op=0 RESULT tag=97  
err=0 text=

Connecting from an RHEL5 client gives me:

Aug 15 16:57:14 csenet slapd2.3[4105]: conn=1326 fd=15 TLS established  
tls_ssf=56 ssf=56
Aug 15 16:57:14 csenet slapd2.3[4105]: conn=1326 op=0 BIND  
dn="<binddn>" method=128
Aug 15 16:57:14 csenet slapd2.3[4105]: conn=1326 op=0 RESULT tag=97  
err=13 text=stronger confidentiality required

I've got the same client configs on both systems, and TLS_REQCERT =  
allow.

The truly confusing part is when I do an ldapsearch (instead of trying