箱田と申します。

> Windows版 mysqladmin の不具合ではないでしょうか？

私の環境はWindows2000＋mysql3.23.53ですが、
mysqladminで問題なくパスの変更ができました。
-----------------------------------------------------------
C:\mysql\bin>mysqladmin --version
mysqladmin.exe  Ver 8.23 Distrib 3.23.53, for Win95/Win98 on i32

C:\mysql\bin>mysqladmin -uroot -p1234 password test

C:\mysql\bin>mysqladmin -uroot -ptest password 1234

C:\mysql\bin>
-----------------------------------------------------------

debianでうまくいったケースも、
> debian:~# mysqladmin --version
> mysqladmin  Ver 8.23 Distrib 3.23.49, for pc-linux-gnu on i686
という事なので、ひょっとしてWindows版云々ではなく、
バージョン依存の可能性もあるのではないでしょうか？

自分の環境ではすぐにmysql4.0を入れられないので、実際にテストできてません。
ですが今までWindows版でうまくいったという報告がなかったので、
参考までに投稿してみました。