Hola
marawa1 y bienvenido a los foros.
Si tu serial el legal no deberías tener problemas, ahora bien, si el que formateó empleó una clave ilegítima y pagaste por ella deberías hablar con él y que lo solucione validando esa copia.
De todas formas puedes intentar ponerte en contacto con Microsoft por teléfono, explicar tu caso, te harán unas preguntas y normalmente no ponen pegas para darte una nueva clave con que activar Windows. Pero lógicamente has de darles el serial actual para que lo comprueben.
Para saber el teléfono de Microsoft en tu zona haz lo siguiente:
Inicio-->Ejecutar-->escribe:
%systemroot%\system32\oobe\msoobe.exe /aTe aparecerá la pantalla "Vamos a activar Windows". Activa la opción de "Llamar por teléfono". En la próxima pantalla elige tu ubicación y te aparecerá el o los teléfonos para ponerte en contacto con ellos.
Pero tu primera opción sería hablar con quién te cobró la licencia. Saludos.

EDITO: Para que no te aparezca de nuevo la "estrellita" desactiva las Actualizaciones automáticas y las descargas manualmente hasta que soluciones la validación, de lo contrario volverá a aparecerte.