[Premature end of script headersの解決法][1]は、エラー時のチェックポイントがまとまっており、困ったときに参考になります。
チェックポイント
1. 改行コード
2. Perlのパス
3. ファイル転送モード
追加情報ですが、Premature end of script headersのエラーなる場合に、Suexec を無効にすると動くことがあります。
[Apache Tutorial: CGI による動的コンテンツ][2]
> Suexec の権限のチェックは非常に厳しく、それを満たさない場合は CGI プログラムが Premature end of script headers エラーで 実行されません。
あるCGIのインストールプログラムが Premature end of script headers になり、調べたところ Suexec が原因で、無効にすることにより動作しました。
そのインストールプログラムが、ファイルのアクセス権を 705 や 707 に変更しているのが問題ではないかと推測しています。(未確認)
[1]: http://sagittarius.dip.jp/~toshi/premature.html
[2]: http://httpd.apache.org/docs/2.0/ja/howto/cgi.html