A partire da mysql 4 (credo), é cambiato il sistema di gestione delle password. Questqa cosa crea dei casini come questo (che tra l'altro é tipicissimo, lo hanno avuto tutti). si risolve semplicemente impostando il vecchio sistema di password.

Da riga di comando:

mysql> SET PASSWORD FOR 'some_user'@'some_host' = OLD_PASSWORD('newpwd');

Più dettagliato:

http://dev.mysql.com/doc/mysql/en/old-client.html