まず、もっとも簡単なCGIを動かしてみてください（パーミッション変更忘れずに）
例

#! /usr/bin/perl
#↑これは各自の環境に合わせてください
print "Content-type:text/html\n\n";
print "test";

これで動かなかったら以下の項目を試してみてください（責任はもてません）

A.あなたがサーバ管理者の場合（B.の借りてる場合も参照）
1、改行コードが誤認識される
　なんか、こういう事態が発生することがあるみたいです。（うちもそうです）
　perl script内の一行目に

　#! /usr/bin/perl --

　を付けるとなぜか直る。
　※FTP転送で相手のOS自動認識がうまくいかないとなるとの報告もありますが、うちではなぜかLinux上で作成した物でもこれをつけないと動かないです＾＾
2、perlのパス表記が間違ってる。
　てきとーにシンボリックリンクでも張って記述が違っても動くようにしてあげましょう。
3、その他
　安定稼動しているApache1.3系に乗り換えましょう（私もそうしました。1の解決法も併用）

B.あなたがサーバを借りている場合
1、ファイル転送モードが間違っている
　Binaryモードで転送すると動かないのでASCIIモードで転送してください。
2、文字コード変換がうまくいってない
　通常FTPソフトは文字コードを自動変換してくれるらしいのですが、うまく言ってない場合もあるとかないとか。
　サーバがLinux系の場合はEUCとかにしてあげるとよいみたいです。
3、改行コードが誤認識される
　2の問題と関連するみたいですが、なんか、こういう事態が発生することがあるみたいです。（うちもそうです）
　perl script内の一行目に

　#! /usr/bin/perl --

　を付けるとなぜか直る。
4、perlのパス表記が間違ってる
　パスを再確認しましょう。SSHなどでログインできる場合は
　%which perl
　などでパスを確認できるかも。わかんなかったら管理者に聞きましょう。
5、その他（おまじないレベル？）

　print "Content-type:text/html\n\n"

　とかの部分の「\n」をたくさん増やしてみる。
　直ったとの報告あり

私の知ってるのはこんな程度です。ちなみに私のはApache2.0系ので全然動かず（mod_perlがおかしかったので直してもhtmlがみれなかったりとか）1.3系に入れなおして1の解決法で直しました。

ちなみに、Premature end of script headersは何か特定の問題を示すに至るエラーではないようです。何かしらの問題で、ちゃんと結果が出力されないときに出るという感じみたいです。

参考になったでしょうか？（汗