Verifique se você definiu o caminho a seguir em /etc/apache2/apache2.conf
:% ScriptAlias /cgi-bin/ "/path/to/cgi-bin/"
e se seus scripts estão nessa pasta.
Se seus scripts terminarem em .pl, certifique-se de alterar a linha de AddHandler cgi-script .cgi
to AddHandler cgi-script .cgi .pl
em /etc/apache2/apache2.conf
e verifique se ele não está comentado.
Options FollowSymLinks +ExecCGI
precisa ser configurado no seu host virtual.