Gracias a lado2mx por el tip, efectivamente la solución era por ese lado.
Por fin después de tanto moverle sin solución, me dediqué a buscar en los foros de mysql.org y encontré la solución, aqui la traduzco para que quede de ayuda si alguien mas cae en mi problema.
################################################## #######################################
# mysql_connect(): Client does not support authentication protocol requested by server; #
# consider upgrading MySQL client #
################################################## #######################################
La solución
##############
Extraída del foro de mysql.org enla liga
http://forums.mysql.com/read.php?11,6400,6731#msg-6731
La idea es hacer que mysql lea la contraseña en la forma vieja, para lo cual, debemos
hacer lo siguiente...
1) Entrar a la consola de mysql y teclear:
mysql> SET PASSWORD FOR usuario@localhost = OLD_PASSWORD('clave_usuario');
2) Buscar el archivo my.ini(que es donde esta la configuración del mysql) dentro de la
la carpeta del sistema del usuario (WINNT, Windows), editarlo e incluirle lo siguiente.
#Use old password encryption method.
old_passwords
3) Reiniciar tanto el apache como el mysql para que los cambios surtan efecto.