Und deine ganze Apache-Konfig ist wirklich in Ordnung?
mal mit apachectl configtest getestet?

Wird denn auch das Modul mod_cgi bzw. mod_cgid geladen?