Si tienes PHP5 considera usar la extensión mejorada (php_mysqli), el problema radica en que la extensión php_mysql que traen las diferentes versiones de PHP es un poco antigua, 3.23.x si mal no recuerdo, y en las versiones del MySQL 4.x me parece que se usa un nuevo sistema de autenticación de usuario, es por eso que te manda el error, aquí tienes la manera como solucionarlo:
http://dev.mysql.com/doc/mysql/en/old-client.html