Podrian ser varias cosas, lo primero que se me ocurre es que el archivo lo subiste a tu server como binario en lugar de subirlo como ascii, intenta borrarlo y subirlo nuevamente como ascii y dale permisos de 775 para poder ejecutarlo.
Tambien podrias revisar que la direccion que le das a tu navegador corresponda a la de tu archivo es decir
http://<tu server>/cgi-bin/<archivo.pl>
Por ultimo podria ser que la ruta del compilador no sea la que especificas en la primera linea, prueba con #!/usr/local/bin/perl
Saludos