AddType application/x-httpd-cgi .cgi

と書いた".htaccess"ファイルを作り、CGIを置くディレクトリに、アスキー転送してみてください。それでも同じエラーがでるようならば、そのサーバーはユーザーにCGIを開放していないということになります。プロバイダに問い合わせてみてください。

perl -ne 'print if /\r/' スクリプト名　リターン

と入力してみます。
もしスクリプトの内容が表示されてしまったなら、改行コードが間違っている、すなわちファイル転送に失敗しているということです。UNIX上でPerlのプログラムを動かすにはファイルはテキストモードで転送しなければなりません。転送し直してください。
表示されなければ改行コードについては問題ありません。

次に、perlのパスを確認します。
whichコマンドを使って、perlのサーバーでのパスを調べます。これをスクリプト内先頭に書いてあるパスと比較してください。
まちがっていませんか？まちがっているならば正しく書きなおしてください。
また、TelnetでCGIを実行して見てください。

sh: ./スクリプト名 : Permission Denied

と表示されたならば、ファイル権限の設定がまちがっています。正しく設定し直してください。