I recently had to upgrade a mysql server from version 4.0.x to 5.0.x and ran into the following issues.
#1 Error Client does not support authentication protocol
This was due to the fact that the mysql client was older than 4.1 and the server was upgraded to 5.0.x and according to the MySQL documentation: MySQL 5.0 uses an authentication protocol based on a password hashing algorithm that is incompatible with that used by older (pre-4.1) clients.
You can either upgrade the mysql client to a version 4.1 or greater or run the following for the user name that needs to connect with a mysql client version of 4.0 or less.
SET PASSWORD FOR->
'In addition, you may need to edit your mysql server to accept old password. You can do this in the /etc/my.cnf file by adding old-password = 1 to the [mysqld] section and restarting mysql. #2 DNS issues. I was getting an error that the username couldn't connect from a particular hostname. To take DNS queries out of the connection, you can add skip-name-resolution to the [mysqld] section of your /etc/my.cnf file and this will tell mysql server daemon to not perform a DNS lookup of the calling IP address. Restart mysql.
some_host' = OLD_PASSWORD('