Thanks Aaron. The Perl version is the same on both environments (5.8.8), however the PATH variable is significantly different:
PATH == /sbin:/usr/sbin:/bin:/usr/bin
PATH == /usr/kerberos/sbin:/usr/kerberos/bin:/usr/local/sbin:/usr/local/bin:/sbin:/bin:/usr/sbin:/usr/bin:/root/bin:/usr/eclipse/eclipse:/usr/local/apache-maven/apache-maven-2.2.1/bin:/usr/java/jdk1.6.0_34//bin
Any of the paths missing in CGI could be causing this?
Also, I have the following variable in shell, but not in CGI
TOMCAT_HOME == /usr/share/tomcat6/