原因はMySQL4.1のパスワードハッシュアルゴリズムっぽい

MySQL 4.1 では、パスワードハッシュアルゴリズムに基づく認証プロトコルが使用されていますが、これは旧クライアントが使用しているものと互換性がありません。サーバを 4.1 にアップグレードすると、旧クライアントで接続しようとした場合に、以下のエラーメッセージが発生する可能性があります。

とりあえずダウングレードして試してみよう。