The mod_negotiation seems to be enabled, but .php files without extensions return 404

I have the following problem - after moving to a new platform PHP files aren't found unless URL contains their extension. So, if /var/www contains file problem.php, the URL http://localhost/problem.php displays correctly, but http://localhost/problem does not. I have tried the following:

• Checked if MultiViews are enabled in the configuration file:

  <Directory /var/www/>
      Options Indexes FollowSymLinks MultiViews
      AllowOverride All
      Order allow,deny
      allow from all
  </Directory>

• Checked if mod_negotiation is loaded via phpinfo():

Loaded Modules: core mod_log_config mod_logio mod_version prefork http_core mod_so mod_alias mod_auth_basic mod_authn_file mod_authz_default mod_authz_groupfile mod_authz_host mod_authz_user mod_autoindex mod_cgi mod_deflate mod_dir mod_env mod_mime mod_negotiation mod_php5 mod_reqtimeout mod_rewrite mod_setenvif mod_status

• Just in case the above was a stress-induced hallucination, tried loading the mod_negotiation2 and restarting the server:

  leviathan www # a2enmod negotiation
  Module negotiation already enabled
  leviathan www # service apache2 restart
    Restarting web server apache2                                                                                             apache2: Could not reliably determine the server's fully qualified domain name, using 127.0.1.1 for ServerName
   ... waiting apache2: Could not reliably determine the server's fully qualified domain name, using 127.0.1.1 for ServerName
                                                                                                                        [ OK ]
  leviathan www # 

• Made sure .htaccess isn't causing this by testing in a directory without .htaccess file.

But all for naught, and I still get 404 errors, and I completely fail to understand why. What am I doing wrong? My platform is Linux Mint 14.