Hola,
Si miras los comentarios de los usaurios en
http://www.php.net/manual/en/function.mysql-connect.php . El problema es que mysql en la version 4.x cambio la forma de encriptar los passwords. Y las aplicaciones clientes (libreria mysql de php, por ejemplo) intentan conectarse usando el metodo antiguo de encriptar claves.
En
http://dev.mysql.com/doc/mysql/en/password-hashing.html tienes algunas posibles soluciones.
Saludos.