If a client receives the subject message while attempting to change their password, you may also have and Event ID 577 in the Security event log.
C00000BE indicates an inability to connect to the PDC, which is required for changing the password.
Try to ping the PDC by IP Address and name. If you can't, try adding a LMHOSTS entry (tip 817 and it's links).
Verify you can issue a NET USE * \\PDCname\ShanreName.
If WINS is installed on the network, verify entries in the primary and secondary WINS server.
Turn off Users must log on in order to change password in User Manager for Domains.
Make sure that HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\LSA\RestrictAnonymous is not set to 1 on the PDC, if you want the user to be able to change their password before logging on.
If the client is running Windows NT 4.0 with SP3, and the PDC or %LogonServer% are Windows NT 4.0 with SP4, see tip 898.