I had my machine do the same thing, but no hardware changes in the last 18 months, and no installs since the last hardware upgrade. All of a sudden one day it was genuine, then the next day it wasn't. Rung Microsoft and found it was trouble with their database somewhere, and nothing they could do about it.
