Deberías indicar que versión de Mysql usas y de PHP ..
Si usas las funciones mysql_xxxx() bajo Mysql 4.1.x o superior .. dichas funciones son y usan el "cliente" para Mysql antigüo .. el cual no acepta usuarios con contraseñas encriptadas. Si que lo acepta si usas mysqli_xxxx() (
www.php.net/mysqli)
Pero, .. puedes cambiar las contraseñas de tus usuarios de Mysql al viejo modo y seguir usando todo como antes:
http://mysql.jcamargo.com/2005/08/14...tion-protocol/
Un saludo,