Barrapunto

Si tu versión de MySQL es 4.1 o superior, debes de tener en cuenta que ha cambiado la forma en la que MySQL encripta las contraseñas, y muchos de los programas cliente (como el driver JDBC de MySQL) pueden no soportar aún el nuevo esquema de contraseñas. Yo tuve ese mismo problema hace unos días y para corregirlo tienes dos opciones:

1. Que descargues una nueva versión del driver JDBC para MySQL que soporte el nuevo esquema de autenticación.
2. Que hagas una pequeña chapuza. Entra a la base de datos y cambia los passwords de los usuarios con la función old_password():

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

Para más info, checate esta liga [mysql.com]