It still looks like Apache isn't set up correctly to parse Perl scripts. The .htaccess trick that Andy suggested may need to be applied to the httpd.conf instead. Apache may be configured to not allow .htaccess overrides. Have you contacted your host yet?
~Charlie
~Charlie