Du musst in der Shell mit a2enmod cgi auch CGI aktivieren.
Hast du schon mal mit apachectl -t und apachectl -S getstet, ob alles stimmt?