RESOLUTION Make sure that Plesk PHPMyAdmin user exists in mysql.user table and has right password and privileges. Username and password can be found in $PRODUCT_ROOT_D/admin/htdocs/domains/databases/phpMyAdmin/config.inc.php (Note, since Plesk 8.1 the file is $PRODUCT_ROOT_D/admin/htdocs/domains/databases/phpMyAdmin/libraries/config.default.php), for example: