Смена пароля юзера тут ни при чём, это два разных механизма. У рабочей станции свой machine account (PCNAME$) со своим паролем в AD, и trust relationship (secure channel) завязан именно на него, не на пароль пользователя. Проверь
nltest /sc_verify:domain.local, чинится без вывода из домена:
Test-ComputerSecureChannel -Repair -Credential (Get-Credential)
. Причину рассинхронизации ищи в DNS на клиентах (только свой AD), дублях имён компьютеров, восстановлении машин из старых snapshot и репликации между DC.