Es algo asi como que desde cierta version en adelante mysql cambió el protocolo de autentificacion entre el cliente (php en este caso) y el servidor. Una solucion es hacer lo que te dice el mensaje, buscar un php mas avanzado que traiga la bibblioteca cliente de mysql actualizada, o esta otra: crear las password de usuario a la manera antigua, te dejo un ink donde se explica:
http://www.webestilo.com/weblog/index.php?p=14