If you got here and you are using Debian/Ubuntu (or any other dpkg based distro), execute the following command:
sudo dpkg-reconfigure phpmyadmin
The phpmyadmin package contains the script to perform this operation for you, all it needs is a user with permissions. sudo is not required if you're logged in as root, of course.
EDIT: It might be worth trying to drop the current phpmyadmin user.