Das mit den Zeilenumbrüchen verhält sich so:

Von vielen Usern werden CGI-Skript unter Windows geschrieben und dann auf einen *NIX-Server geladen.
Unter Windows werden die Zeilenumbrüche als \r\n dargestellt, unter *NIX nur als \n. Wenn man dann das Skript im binary-Modus hochlädt, werden die \r\n nicht in \n umgewandelt, sondern bleiben erhalten.

Wenn jetzt das Skript gestartet wird, wird die Shebang ausgewertet. In der steht dann aber nicht nur #!/usr/bin/perl sondern #!/usr/bin/perl\r. Und dieses Programm gibt es nicht...

Du solltest die Rechte übrigens auf 755 setzen und nicht auf 777!