client does not support authentication...."
In my phpinfo(); the version of mysql cilent was set 3.23.58, but when I want to upgrade it with the new one, "this package is already installed" was indicated. At first FC2 installed MySQL 3.23 for me, then I upgraded it.
I answer this question on such a regular basis that I have a FAQ entry for it.
It details the cause and solution of the error you have encountered.
This was first published in June 2005