Hmmm... that seems really wierd ... could you do something like this and post the results?

Plankton@linux:~/perl/perlmonks> which perl
/usr/bin/perl
Plankton@linux:~/perl/perlmonks> ls -l badshebang.pl 
-rwxr-xr-x    1 Plankton users          40 2004-04-20 19:34 badshebang
+.pl
Plankton@linux:~/perl/perlmonks> ./badshebang.pl 
bash: ./badshebang.pl: /usr/local/bin/perl: bad interpreter: No such f
+ile or dir
ectory
Plankton@linux:~/perl/perlmonks> cat badshebang.pl 
#!/usr/local/bin/perl
print "WooHoo\n";
Plankton@linux:~/perl/perlmonks> cat goodshebang.pl 
#!/usr/bin/perl
print "WooHoo\n";
Plankton@linux:~/perl/perlmonks> ./goodshebang.pl 
WooHoo
Plankton@linux:~/perl/perlmonks> ls -l `which perl`
-rwxr-xr-x    2 root     root      1257284 2003-03-13 14:33 /usr/bin/p
+erl
[download]

Somethings to look for ... 1) is the perl file a actual executable or a symbolic link to the real perl executable? 2) Are you somehow having that aynoning ^M problem ... you know

#!/usr/bin/perl^M
[download]

Also you might find node(#! question) helpful.