Descobri que a adição de um usuário que ainda não tenha seu certificado armazenado em cache no servidor falhará.
Eu resolvo isso executando uma janela CMD como esse usuário (Executar como um usuário diferente) e, em seguida, usando o cipher.exe nesse contexto para criptografar um único arquivo.
Essa operação armazena em cache o certificado do usuário no servidor, portanto, fecho esse CMD e retorno à minha linha de comando "normal". Operações subseqüentes / ADDUSER são OK depois disso.
Espero que ajude,
Thomas