Aqui está a causa que encontramos:
Um servidor foi configurado para usar o Navy Timeserver. Que teve uma falha e fazer com que o servidor mostre o ano 2000.
"On Monday, November 19, USNO made what was expected to be a routine upgrade. Unfortunately, for 51 minutes, between 21:07:32 - 21:58:56 UTC, the server gave out the year as 2000 instead of 2012. We have resolved the issue that caused this error." (http://tycho.usno.navy.mil/ntp.html, 11/27/2012)
Isso fez com que o controlador de domínio que tinha esse servidor de tempo informasse ao outro servidor durante um longo período que não era confiável (tempo suficiente para uma perda permanente de confiança).
Infelizmente, a única solução foi rebaixar de forma forçada o controlador de domínio e promovê-lo novamente.
De nota adicional: Usando 3 vezes diferentes servidores de tempo teria evitado isso; nós estaremos fazendo isso no futuro:)
Obrigado!