I am another newbie and had the same problem. I have a user 'pma'. I have set up a database 'phpmyadmin' and populated it using the script create_tables.sql. All the tables are there in the database. So far so good.
Then in config.inc.php I inserted the following text which I copied from config.sample.inc and then edited (I put in the actual password for user pma in place of the asterisks).
/*
* phpMyAdmin configuration storage settings.
*/
/* User used to manipulate with storage */
$cfg['Servers'][$i]['controlhost'] = '';
$cfg['Servers'][$i]['controluser'] = 'pma';
$cfg['Servers'][$i]['controlpass'] = '********';
/* Storage database and tables */
$cfg['Servers'][$i]['pmadb'] = 'phpmyadmin';
$cfg['Servers'][$i]['bookmarktable'] = 'pma_bookmark';
$cfg['Servers'][$i]['relation'] = 'pma_relation';
$cfg['Servers'][$i]['table_info'] = 'pma_table_info';
$cfg['Servers'][$i]['table_coords'] = 'pma_table_coords';
$cfg['Servers'][$i]['pdf_pages'] = 'pma_pdf_pages';
$cfg['Servers'][$i]['column_info'] = 'pma_column_info';
$cfg['Servers'][$i]['history'] = 'pma_history';
$cfg['Servers'][$i]['table_uiprefs'] = 'pma_table_uiprefs';
$cfg['Servers'][$i]['tracking'] = 'pma_tracking';
$cfg['Servers'][$i]['designer_coords'] = 'pma_designer_coords';
$cfg['Servers'][$i]['userconfig'] = 'pma_// $cfg['Servers'][$i]['recent'] = 'pma_recent';
/* Contrib / Swekey authentication */
$cfg['Servers'][$i]['auth_swekey_config'] = '/etc/swekey-pma.conf';
I saved the edited config.inc.php and restarted phpMyAdmin and the error message had disappeared. Bingo!
I hope that this helps people. I am using phpMyAdmin 3.5.5, which is the current one. Windows 7.