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