The bug is only in the libcrypt-ssleay-perl package version 0.29-3. It was compiled on a Debian Woody (Perl 5.6.1) system instead of Debian Sid (Perl 5.8.0). It has a bad dependency because of this.

Since you are running Red Hat, I do not see how the two could be related. Unless you are doing some really funky package installs. ;)