Is my Perl (5.6.1) just too old to be built on RHEL4AS?

Quite likely. The main reason 5.6.2 was released was that 5.6.1 no longer build with certain newer versions of certain compilers. And considering that commercial vendors usually understand the value of backwards compatability much better than many open source products, I wouldn't be at all surprised if was gcc that triggered the release of 5.6.2. And RedHat uses gcc.

Is there a reason you need 5.6.1? Or even 5.6.2? 5.6.1 is 8 years old. That's not as old as the perl6 effort, but perl5 has progressed quite a bit in the past 8 years. You might want to try 5.10.0 or 5.8.9 instead.