Got this irritating message when I was working with a simple PHP /MySQL app I was trying out
Client does not support authentication protocol requested by server; consider upgrading MySQL client
I just changed the database username for the application and the error went missing
http://dev.mysql.com/doc/refman/5.0/en/old-client.html has some thoughts on the same