Client does not support authentication protocol ってMySQLに言われた場合

Client does not support authentication protocol requested by server; consider upgrading MySQL client

http://dev.mysql.com/doc/refman/4.1/ja/old-client.html

上記では「MySQL 4.1 では・・・」ってことで、自分環境は MySQL 5.1.56 なのでちょっと府に落ちないが、

mysql> UPDATE user SET Password = OLD_PASSWORD('設定するパスワード') WHERE Host = 'localhost' AND User = 'root';
mysql> FLUSH PRIVILEGES;

ってすると一応解決した。