The reason is this:

MySQL 5.0 & MySQL 4.1 use an authentication protocol based on a password hashing algorithm
that is incompatible with that used by older (pre-4.1) clients.
If you upgrade the server from 4.1, attempts to connect to it with an older client may fail with the following message:

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

So what are the possible fixes ?

The obvious one, which is not the most practical in the middle of an emergency is to upgrade
the client to the latest MySQL 4.1 or 5.0 Client, which could be problematic cause in the case
of a webserver with PHP means recompiling PHP, but if you have the time you might as well do it.

The other solution which is the one I used is to change the password of the user you are connecting
with, from the new format to the old format,there is a function in MySQL 4.1 & 5 to do this,

SOLUTION

Connect to MySQL client on new database server and run:

mysql> UPDATE mysql.user SET Password = OLD_PASSWORD('newpwd')
    -> WHERE Host = 'some_host' AND User = 'some_user';

For example

mysql> update mysql.user SET password = OLD_PASSWORD('felipepass') where host = '%' and user = 'felipe';

After that then flush privileges

mysql> flush privileges;

Hope it was usefull.
Felipe