Clique com o botão direito do mouse no ícone "Computador" (se não estiver na área de trabalho, ele deve aparecer no menu Iniciar) e escolha "Propriedades" (ou no Painel de Controle {visão de ícones} escolha "Sistema"). A tela que aparece deve ter uma opção próxima à parte inferior (talvez você precise rolar a tela para baixo, dependendo da resolução da sua tela) que diz "Alterar chave do produto".
Após inserir a nova chave do produto, você precisará "ativar" sua licença. Nesse momento, você descobrirá se a Microsoft considera legítima.
Quando você instala uma licença do Windows para 1 usuário em duas máquinas, esse tipo de mensagem de erro é exibido. É bom que você tenha uma segunda licença que possa usar (desde que não esteja sendo usada em nenhum outro lugar).