Deberías indicar que versión de PHP que estás usando .. pero el error lo que indica ese que estás usando la versión del cliente de Mysql para PHP "vieja" .. donde la gestión de usuarios de Mysql y sus contraseñas concretas no son iguales a las versiones anteriores de Mysql (4.0) hacia abajo.
Revisa la documentación oficial de Mysql para que veas como cabiar las contraseñas de tus actuales usuarios de Mysql al sistema antigüo de contraseñas de Mysql:
http://dev.mysql.com/doc/mysql/en/Old_client.html
También el mensaje de error te dá una sugerencia .. "actualizar" tu "cliente" .. Se refiere ya que usas PHP a que no uses las funciones mysql_xxxx() (
www.php.net/mysql) sino las funciones mysqli_xxxx() (
www.php.net/mysqli) que es el nuevo "cliente" de Mysql para PHP (en forma de extensión que hay que habilitar a PHP).
Un saludo,
PD: .. y Si, hay un foro sobre "Base de datos" y un sub-foro dedicado enteramente a "Mysql" .. donde voy a mover este mensaje aprovechando.