片寄です。

> rootで新規のユーザを作成しようとするとエラーになってしまいます。

> Your MySQL connection id is 110 to server version: 4.0.18-standard

> mysql> grant all on *.* to uuuu identified by 'uuuu' ;
> ERROR 1036: 'user' は読み込み専用です

あまり的確な回答か不安ですが、多分、何らかの原因で
ユーザrootにはテーブル'user'に書き込み権限がないのでしょう。

select Host,User,Grant_Priv from MySQL.user where User='root';

でGrant_Privが'Y'になっているのでしょうか