[HLT]

Event log что говорит на тех машинах, на которых пароль не меняется?

Вдогонку: те машины, на которых не получается сменить пароль, - чем-то отличаются от тех, на которых всё нормально? Может, на них какая-то особая групповая политика применяется?

У Вас домен не с NT мигрировавший? Сразу 2000 был? Тогда дальше можно не читать.
Если мигрировавший с NT - может быть такая фигня:

When you attempt to change your expired domain password from a client workstation, the Access Denied error message appears. This problem occurs when "Users Must Log On In Order To Change Password" is selected in the User Manager for Domains Account Policy dialog box.

Читаем дальше:http://support.microsoft.com/kb/255776
То есть эта политика была в NT, но в 2000 её убрали. Если домен мигрировал с NT - могло остаться...
(вот такие досужие домыслы)