I followed this tutorial in installing Bugzilla, I didn't encounter any problem not until I hit localhost/bugzilla in the URL. My sites-available/default config is as follows:

    #ScriptAlias /cgi-bin/ /usr/lib/cgi-bin/

    Alias /bugzilla/ /var/www/bugzilla/

    <Directory /var/www/bugzilla>

            AddHandler cgi-script .cgi .pl

            Options +Indexes +ExecCGI +FollowSymLinks

            DirectoryIndex index.cgi

            AllowOverride Limit

    </Directory>

    #<Directory "/usr/lib/cgi-bin">

    #       AllowOverride All

    #       Options +ExecCGI -MultiViews +SymLinksIfOwnerMatch

    #       Order allow,deny

    #       Allow from all

    #</Directory>

And when tailing at var/log/apache2/error.log

(13)Permission denied: exec of '/var/www/bugzilla/index.cgi' failed

From comments ...

ls -l -rwxr-x--- 1 root apache2 2.6K Feb 20 01:16 /var/www/bugzilla/index.cgi