How to set up cgi-bin properly in apache2?

Question

I just set up a fresh apache2 with these Options for CGI:

ScriptAlias /cgi-bin/ /var/www/cgi-bin
<Directory "/var/www/cgi-bin">
  AllowOverride None
  Options +ExecCGI -MultiViews +SymLinksIfOwnerMatch
  Order allow,deny
  Allow from all
  AddHandler cgi-script cgi pl 
</Directory>

I created the directory at /var/www/cgi-bin, added the scripts, made them executable, restarted the server, but it still says gives a 404 when trying to access the scripts.

Any ideas?

(Ubuntu 12.04 LTS)