鈴木です。こんばんは。

>マイグレーションというか、既存のものをバージョンアップした
>ならこの話はわかるのですが、全く新規にインストールしているの
>に、この問題？が提起されるのは何故なのでしょうか。

あくまでも私の予想ですが、MySQLへの外部接続ツールは、パスワードの仕組み
が違う、バージョン4.1とそれより前のバージョンの両方への接続を実現しなく
てはなりません。
それを実現するには、両方の仕様に対応しているか、前のバージョンに合わせる
か、だと思います。

つまり、本体のMySQLの問題ではなく、外部接続ツールの問題だということです。
MySQL Administratorなるツールを使ったことがありませんが、似たツールで、
かねやんMySQLAdminというツールを使用したことはあります。
クライアントがWindowsかつ、MySQLクライアントをインストールしている場合は、
コマンドプロンプトからも接続ができます。

mysql -h (ホスト名 | ＩＰアドレス) -uユーザ名 -pパスワード


OLD_PASSWORDを使用する具体的なコマンド例は、以下のようなものです。

UPDATE USER SET PASSWORD = OLD_PASSWORD('mypass01') WHERE USER = 
'user01' AND HOST = '192.168.1.%'; 
FLUSH PRIVILEGES; 


上記コマンドの前提条件。
192.168.0.%/255.255.255.0のローカルネットワーク環境。
外部接続を許すユーザーは、user01というユーザー。
そのパスワードは、mypass01。


シツコイかもしれませんが、グーグルでも「mysql old_password」キーワードで
たくさんの例が出ますので、そちらの方が多様な例が得られますし、速いです。