I have to think that the “Client does not support authentication protocol” error message may be the single most common error ever encountered for MySQL. While it’s not exactly coming back in 5.6, those users who have implemented workarounds in support of older client libraries will find they need to add an additional step if they upgrade to 5.6. This is because in 5.6.5, a change was made to default the secure_auth option to ON. Here’s what the manual has to say about this:

This option causes the server to block connections by clients that attempt to use accounts that have passwords stored in the old (pre-4.1) format. Use it to prevent all use of passwords employing the old format (and hence insecure communication over the network). Before MySQL 5.6.5, this option is disabled by default. As of MySQL 5.6.5, it is enabled by default; to disable it, use --skip-secure-auth.

The pre-4.1 password hashing has been deemed inadequate for years; that’s the reason password hashing was overhauled in 4.1, causing so much pain.  Hopefully, the lessons from 4.1 were applied, and people heard the message that reliance on clients supporting only the older password hashing is a bad thing, and have taken the steps needed to migrate to newer client libraries.  The workarounds for OLD_PASSWORD() and the like were meant as temporary stop-gaps, introduced in 2004 (or earlier) to prevent applications from being completely unable to access MySQL after an upgrade, when there were not yet updated client libraries.  They were not meant to become permanent deployment configurations , but it’s always tempting to not touch something once you’ve found a workaround.

It’s worth checking to see if that’s the case with your deployment.  While you’re at it, you might check for accounts that have no passwords, and just out of curiosity, list the accounts configured to use authentication plugins:

SELECT
COUNT(*),
IF(plugin = '', IF(LENGTH(password) = 16, 'OLD',
IF(password = '', 'NONE', 'NEW')), plugin) format
FROM mysql.user
GROUP BY format;

If you have any user accounts that have LENGTH(password) = 16 and a blank plugin column, that account will be unable to access MySQL 5.6.5 and higher without making some changes.  It’s strongly recommended that you migrate to a more robust password hash (and client library, where needed), but if needed, you can start MySQL with the –skip-secure-auth argument (“skip_secure_auth” for config files).
You will see warnings when you configure user accounts to use older passwords:

mysql> SET PASSWORD FOR ancient@localhost = OLD_PASSWORD('test');
Query OK, 0 rows affected, 1 warning (0.00 sec)

mysql> SHOW WARNINGS\G
*************************** 1. row ***************************
Level: Warning
Code: 1287
Message: 'pre-4.1 password hash' is deprecated and will be
removed in a future release. Please use post-4.1 password hash instead
1 row in set (0.02 sec)

Like the change in 4.1, which trumpeted “Client does not support authentication protocol” when trying to connect without configuring the server to accept old passwords, you’ll get a distinct error message when you try to connect to a pre-4.1 account and have not  started the server with –skip-secure-auth:

D:\>mysql-5.6.5-m8-win32\bin\mysql -uancient -ptest -P3307
Warning: Using a password on the command line interface can be insecure.
ERROR 1275 (HY000): Server is running in --secure-auth mode, but 
'ancient'@'localhost' has a password in the old format; please change 
the password to the new format

In testing, I noticed a couple of other behaviors I hope we’ll tweak before 5.6 GA in order to provide better visibility to this change:

• mysql_upgrade should report a warning when it finds a user account configured to use a pre-4.1 password (Bug#65461)
• mysqld should warn when started with –skip-secure-auth (Bug#65462)
• mysqld should warn (in error log) when a connection is attempted against an account configured for pre-4.1 password and –skip-secure-auth is not in effect (Bug#65463)

This is more good work from the MySQL Engineering team (yay Joro!), and pushes MySQL further from the pre-4.1 legacy of insecure passwords.  If you’re still dependent upon pre-4.1 passwords, the upgrade to 5.6 will be one more opportunity to convert your user accounts to more secure authorization options.