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

Not from my experience. I'm slowly migrating a redhat 7.2 server on to a system with a proper migration path for code and so on, so I've had to build 5.6 several times now. Works fine every time.

I use CentOS, so theres not much difference at all between my systems and yours:

$ perl -v
This is perl, v5.6.2 built for i686-linux

$ uname -a                                                            
+                                                          
Linux dev.waveright.com 2.6.9-78.0.5.ELsmp #1 SMP Wed Oct 8 07:12:03 E
+DT 2008 i686 i686 i386 GNU/Linux

$ cat /etc/redhat-release 
CentOS release 4.7 (Final)

$ gcc -v
Reading specs from /usr/lib/gcc/i386-redhat-linux/3.4.6/specs
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --
+infodir=/usr/share/info --enable-shared --enable-threads=posix --disa
+ble-checking --with-system-zlib --enable-__cxa_atexit --disable-libun
+wind-exceptions --enable-java-awt=gtk --host=i386-redhat-linux
Thread model: posix
gcc version 3.4.6 20060404 (Red Hat 3.4.6-10)
[download]

regards,

UPDATE: I get source code from here.