Yup, you hit the nail on the head. That's exactly what happened. They compiled Perl in the /tmp area and shipped it in another set of directories. I added export PERL5LIB=/path/to/perl/lib/perl5/5.6.1 to my .profile and it worked like a charm.
Now, as to your other suggestion, I'm off to go find a big ol' whacking stick.