Your problem is that Win32 systems use a \r\n for a line terminator, but Unix like systems only use the newline. One way to fix this is to FTP the scripts over in ASCII mode, or use the following one-liner on the script:
perl -pi.bak -e 's/\r\n/\n/' script.pl
The reason it doesn't find Perl without the command line switch is that it is actually looking for 'perl\r', but adding the switch puts whitespace after 'perl', thus allowing it to work. Regardless, I've found that even adding the switch can still cause scripts to fail mysteriously if the line-endings are wrong. Best to strip them.
Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.