Eu gostaria de poder comentar, mas como não posso, vou ter que colocar isso como resposta.
Vou dar uma olhada no LockOutStatus ( link ) e veja em qual CD esse usuário está bloqueado. Pode ser que o usuário redefina sua senha em um DC e depois seja autenticado em outro. Dependendo de quanto tempo o DC se replica, esse usuário pode estar se autenticando em um DC que não obteve a nova senha.
Eu verificaria o status na replicação fazendo:
repadmin /replsummary
em um DC.
Talvez aumente a frequência da replicação entre o DC para mais freqüentes ( link ) ou AD sites e serviços não estão configurados corretamente com a sub-rede e sites ( link ).