So, am I right in assuming that Perl has gotten "disconnected" from the gcc it was configured to use?
Yes. From the listing you provided, I would say that somebody fouled up the system for whatever reason. Run rpm -qifl /usr/lib/gcc/4.1.1 and rpm -qfl /usr/lib/gcc/4.1.2, perhaps you will find a gcc binary that corresponds to the version you need. If there is, you could link that binary to ~/bin/gcc and have ~/bin first in your $PATH. That would be a quick fix.
But what you probably should do is: Record the package details and installation date of the gcc RPMs and write your Sys Admins & their bosses that such a system is inacceptable.