このエラーは、MySQL 4.1 以降で採用された新しいパスワード暗号化形式を利用しているが、 DBD::mysql モジュールが古い MySQL に対してコンパイルされている時に発生します。 DBD::mysql を現在の MySQL ライブラリとコンパイルすることで、 (もしくは単にモジュールの新しいバージョンをインストールする) エラーは消えるでしょう。
この操作でも問題が再発する場合、もしくは既存のモジュールを再コンパイルできない場合 (たとえば Windows 環境下であるなど)、もしくはモジュールをリプレースしたくない場合、 MySQL ドキュメント http://dev.mysql.com/doc/mysql/en/Old_client.html のワークアラウンドを参照してください。