El segundo mensaje es medio irrelevante. Es el resultado esperado de una conexión fallida, o de una consulta fracasada por alguna razón.
Pero lo más relevante es lo que dice @jomaruro:
Cita: Client does not support authentication protocol requested by server
Eso significa simple y sencillamente que el cliente pHP que estás usando no soporta el protocolo de conexión del servidor.
La pregunta es, entonces: ¿Qué estás usando? ¿Qué versión de PHP, y qué librería para MySQL usa ese PHP?
¿Qué paquete usaste para instalar el conjunto MySQ+PHP+Apache?
Parecería que la cosa anda también por allí...