Sorry, I never used RH since 5.1 so I don't know it's security policy...
Normally one could always telnet a port on the machine and get someting back like a connected status, but I get connection refused...
Well, actually these days you can telnet a port only if there's a daemon/service waiting for you on the target. What host did you try to telnet to? If it's your box, it's probably not configured to act as a ldap server
Can you ping the ldap server you're trying to connect to?
If so, try these lines as root:
iptables -A OUTPUT -d <ldap-server-ip> -j ACCEPT
iptables -A INPUT -s <ldap-server-ip> -j ACCEPT
This will allow ANY connection to/from your ldap server, so is somewhat unsafe, but will quickly show if it's a local firewalling problem.
Then try a search.
Note that iptables chains are not persistent, so don't worry too much about messing things: your iptables will go back to previous state after reboot.
Tell me if this solved, in case I might help you find a more "secure" setup.
Here is an iptables howto, only if you feel brave or courious: