Isso ocorre porque a conta NETWORK SERVICE não recebe os direitos de usuário apropriados.
Procure no este artigo no MS, se o servidor não for um DC, use o Método 1 ou o Método 2. Se o servidor é um controlador de domínio, use o método 3 ou o método 4.
Não confunda que o artigo trata dos Serviços de Terminal, instruções que se aplicam a qualquer serviço (qualquer serviço configurado para iniciar usando a conta NETWORK SERVICE pode apresentar sintomas semelhantes).