Alguna vez me ocurrió algo similar y lo solucioné cambiando los passwords de mis usuarios con las instrucciones SET PASSWORD y OLD_PASSWORD.
Código:
mysql> SET PASSWORD FOR
-> 'some_user'@'some_host' = OLD_PASSWORD('newpwd');
En está página puedes enncontrar más información al respecto
http://dev.mysql.com/doc/refman/5.0/en/old-client.html
Saludos