¿Pero has hecho la activacion telefónica? Es que puede ser eso, yo la he tenido que hacer siempre que he formateado mi actual portatil y ningún problema.
Aunque como bien dicen algunos compañeros, es posible que el SP1 sea la cuestión, y que le hayas metido el SO con el SP1 ya incluido.
De todas formas, ¿Como has reinstalado el SO? ¿Con un USB? ¿CD? Si te venía instalado de frica deberías tener un boton o pulsar una tecla F que te lleve a algun menú de recuperacion, formateo, etc... ¿Lo hiciste así? Porque all hacerlo así no hay problema alguno.