Bueno, esto no es un gran problema, la verdad soy tecnico en computadoras, y es un problema frecuente, muchos madarian formatear su maquina, pero es costoso (depende del tecnico), pero para que carajos te dijo eso si eso tiene solucion y es muy sencilla, SIMPLEMENTE TIENES QUE VALIDAR TU WNDOWS es un truco, un hack al sistema operativo, funciona bastante bien y no te demoras mas de 5 minutos, tu pc funcionara normalmente y no tendras inconvenientes a futuro.
En este link veras un video de lo que te hablo, http://www.youtube.com/watch?v=xXdbuciZAsQ.
He realizado esta operacion miles de veces y me ha funcionado de maravilla. eso si te recomiendo que desactives la opcion de actualizaciones, ya que si colocas un programa no original o descargas uno y lo instalas, microsoft por medio de las actualizaciones se dara cuenta y te pasara nuevamente el mismo error.
Podras descargar el programa mediante cualquiera de estos Links:
http://www.megaupload.com/es/?d=Q04WMDHX
http://rapidshare.com/files/101890600/Windows_XP_CD_Key_Changer.rar.html
Recuerda una cosa, no siempre tienes que formatear tu maquina y si la formateas vas perdiendo capacidad en el disco duro, es por eso que aparecen todos estos hack, asi que es mejor que preguntes como lo estas haciendo antes.
Te deseo mucha suerte, es demasiado sencillo, asi que adelante, se que te va a funcionar