I just installed RedHat 6.2 on a bunch of workstations, and faced the same problem. My procedure was:

rpm -qa | grep perl   # I can never remember the name of the RPM
rpm -e --nodeps perl-5.0053-whatever.rpm
rm -rf /usr/lib/perl5
[download]

Then I went to the NFS-mounted directory where I had built 5.6 and did a make install.

This has the nice secondary effect of having Perl installed in the same way on my RedHat and other machines, i.e. the library is in /usr/local/lib/perl5 everywhere.