While you say that open_basedir is commented out, what is the output of phpinfo()? There should be an open_basedir setting in there. And perhaps there is an .htaccess file—or another php.ini config—that is setting open_basedir somewhere.  That said, according to the official phpMyAdmin docs:
Since version 2.2.4, phpMyAdmin supports servers with open_basedir
  restrictions. However you need to create temporary directory and
  configure it as $cfg['TempDir']. The uploaded files will be moved
  there, and after execution of your SQL commands, removed.
So while you say that open_basedir is commented out—implying it is not being used—perhaps you should open up your phpMyAdmin config and set the cfg_TempDir to point to /var/tmp.  The config.php file is located here in Ubuntu 12.04:
/usr/share/phpmyadmin/config.inc.php
Note that the error message refers to /tmp/ but you are referring to /var/tmp/.
Additionally, the issue seems to be covered here in the community wiki reference for PHP related error:
The fix is normally to change the PHP configuration, the related
  setting is called open_basedir.
Sometimes the wrong file or directory names are used, the fix is then
  to use the right ones.
So in your case you can perhaps adjust the php.ini to have this setting:
open_basedir "/var/tmp/:/tmp/:/"
And note that the only php.ini that matters in a case of web related issues like this is /etc/php5/apache2/php.ini.  The CLI php.ini located here /etc/php5/cli/php.ini is strictly for CLI use and has nothing to do with the Apache PHP module.