Some time in the past, during an upgrade to the MySQL software here, I somehow missed a step and didn't upgrade privileges properly, and after upgrading to PHP 5.3, have now finally gotten the dreaded 'mysqlnd cannot connect to MySQL 4.1+ using old authentication' error when launching phpmyadmin. A lot of googling failed to identify an easy fix, but did yield a few clues.
Some time back, MySQL expanded the 'user' table of the 'mysql' database to allow for longer password hashes. But it seems that new hashes weren't generated, and the shorter hashes were still in place for those old user accounts So, ultimately, the fix was simple, just reset the passwords for the old user accounts, using the same passwords, which would update the hash to the new longer version.
If in doubt, the following MySQL commands will show the critical fields:
mysql> use mysql
mysql> select host, user, password from user;
This will show the above fields, the shorter password hashes are 16 bytes long, the newer version is 41 bytes in length. All you need to do is update any of the shorter ones and you're done!