Хорошая статья попалась на тему восстановления доверительных отношений между рабочими станциями и контроллерами домена:
http://implbits.com/About/Blog/tabid/78/post/don-t-rejoin-to-fix-the-trust-relationship-between-this-workstation-and-the-primary-domain-failed/Default.aspx
Оказывается, в случае поломки доверия перезаводить машину не обязательно. Для успешного выполнения процедуры на машине должен быть установлен RSAT или серверные оснастки включающие в себя утилиту netdom.exe