ほかのWindowsマシンから名前解決できないのは、Windows端末が参照している
DNSサーバに問い合わせても名前が返ってこないからだと愚考しています。

この推測がたぶん正解でしょう
それに沿って解決策を探るなら、当該 ubuntu マシンの名前を、Windows 端末が参照している DNS サーバーに登録するだけでしょう
当該 ubuntu マシンが IP アドレスを DHCP で動的に取得している場合は、ubuntu マシン上の DHCP クライアント ソフトウェアの設定を触って、IP アドレスを取得するときにホスト名を DNS に登録するようにする必要があるかも知れません

Windows端末はほぼすべてActive Directoryに所属しています。
ひとつのWindows Server 2003 workgroup端末は名前解決できており

Active Directory に所属しているのに「workgroup」というのは不可解さは、とりあえず無視しておきます

回答ありがとうございます。

進捗は全然ないのですが・・・

お返事から解釈しますと、各Windowsマシンが参照している
DNSサーバに登録がない、もしくはなんらかの理由で登録を拒否
されているということでしょうか。

Windowsマシンの場合適正に
参照DNSサーバ(おそらくADコントローラと同じ）
がクライアントに登録されていれば、勝手に
DNSサーバの名簿が更新されるということでしょうか。

あと下記の件ですが、
>Active Directory に所属しているのに「workgroup」というのは不可解さは、
>とりあえず無視しておきます

これは前の文の中の
「Windows端末はほぼすべてActive Directoryに所属しています。」の"ほぼ"以外の例外に該当します。
言葉足らずで済みません。

>当該 ubuntu マシンの名前を、Windows 端末が参照している DNS サーバーに登録するだけでしょう

resolv.confに登録するだけで勝手にサーバ側に同期されるということはないのでしょうか。
ええと、でも人の手を介する（手続き等が必要）なら手間がかかるという怠け者の事情にすぎません。
調査いたします。

>当該 ubuntu マシンが IP アドレスを DHCP で動的に取得している場合は、
>ubuntu マシン上の DHCP クライアント ソフトウェアの設定を触って、
>IP アドレスを取得するときにホスト名を DNS に登録するようにする必要があるかも知れません

DHCPを使用していないのですが、DHCPサーバを立てれば可能かもしれないということでしょうか。
もしくはDHCPクライアントの設定で可能？
無知な質問ばかりで申し訳ありません。