A causa deste problema é que a senha não atende aos requisitos mínimos de senha, como o passfilt.dll.
Eu encontrei alguns hotixes da Microsoft que pareciam estar relacionados, mas não exatos. Alguém que costumava trabalhar com servidores reconheceu os sintomas imediatamente.
Eu esperava incluir os KBs que estavam diretamente relacionados a esse problema específico, mas não consegui encontrar nenhum.
Esse parece ser um método muito ruim de lidar com problemas de senha, derrubando todo o domínio.