Did you upload in ASCII? Are the permissions correct? Is the perl binary really at /usr/local/bin/perl?

Update: Doh, I should refresh threads before replying. To add something of actual value, I'll mention The Idiot's Guide to Solving Perl CGI Problems. The tone is, well, not exactly the friendliest possible, and a scant few points need updating, but it's an extremely comprehensive compilation of all the little traps one may run into when trying to run a CGI script. Odds are (just like it says) that 99% of the time just checking all the questions there will fix the problem.

Update 2: Doh! Beaten to the punch again. Sigh :)

Makeshifts last the longest.