This was encountered with several accounts that had existed from our OS/2 days and been migrated with a 3rd party tool to NT that preserved their passwords. The users never changed their passwords. When Active Directory was installed this error started appearing. The users were able to authenticate on the LAN but RAS authentication failed. The solution is simply to reset their password -- it can even be the same password; all that has to happen is the password encryption needs to be updated.
This error happens when a user logs on, is allowed to log on, but cannot use any mapped drives or other services secured against Active Directory.
Changing the password at the Active Directory MMC does not seem to fix this, it has to be reset by the user at a PC.
Client can logon to PC but will be challenged for authentication to network servers. This only affects logon from Kerberos aware machines. Kerberos tickets granted to users are based on NTLM hash. NTLM hash is only generated when a password is changed from an NT or W2K box, so users of W9x boxes that switch to W2K Pro after a Domain NT to W2K In-Place Upgrade are likely to be affected. Verify NTLM hash exists with L0phtCrack (thanks to the guys and gals from @Stake).
Resetting the pwd from a W2K or NT box will correct this problem.
The error was fixed in our environment by upgrading to W2K SP3.