つまり、、、よくあるケースというのが
改行コードが Windowsだと \r\n Unix系だと \n
で、
#!/usr/bin/perl\r\n
だと、 perl\r というコマンドを実行しようとして、そんなものは無い、と言われるわけ
もしそうならば、ftpでasciiモードで転送するか変換するのがいいけれど、
#!/usr/bin/perl --\r\n
とやれば、少なくとも perlは存在するので実行できる、というわけ

もし改行コードに問題が無ければ別の要因を探るしかないかな