Algo que nunca foi mencionado em nenhum tutorial, ou qualquer uma das minhas pesquisas estava ativando o módulo CGI.
sudo a2enmod cgi
sudo service apache2 restart
Para referência, aqui está o meu apache2.conf:
Alias /bugzilla/ /var/www/html/bugzilla/
<Directory /var/www/html/bugzilla>
AddHandler cgi-script .cgi
Options +ExecCGI +FollowSymLinks
DirectoryIndex index.cgi
AllowOverride Limit FileInfo Indexes Options
</Directory>
Fonte: link