FYI para qualquer um que encontre essa pergunta no futuro. Consegui resolvê-lo assim:
- (1) Faça logon em outro não-DC no domínio
- (2) Faça logon como um domínio admin
- (3) Instalar / adicionar as ferramentas do RSAT (as do AD em particular)
- (4) Inicie a ferramenta AD do PowerShell
- (5) Execute o Add-KDSRootKey a partir da nova máquina.
Espero que isso ajude alguém