This error is occurring because you are using the new password encryption that comes with MySQL 4.1, while your DBD::mysql module was compiled against an older version of MySQL. If you recompile DBD::mysql against the current MySQL libraries (or just obtain a newer version of this module) then the error may go away.
If that does not fix the problem, or if you cannot recompile the existing module (e.g. you're running Windows) and/or don't want to replace it (e.g. you want to keep using a packaged version), then a workaround is available from the MySQL docs: http://dev.mysql.com/doc/mysql/en/Old_client.html