[Fri Apr 24 19:15:34 2009] [error] [client 127.0.0.1] (2)No such file or directory: exec of '/path/to/script.cgi' failed
[Fri Apr 24 19:15:34 2009] [error] [client 127.0.0.1] Premature end of script headers: script.cgi

ということで、script.cgi の1行目Perlへのパスを書き換えた。

#!/usr/local/bin/perl

から 

#!/usr/bin/env perl

へ。

ココを疑うのを忘れることがある。