Howdy, I work in the Scandinavian activation centre for Microsoft and I can tell you that this isnt the first time we have heard this.
This happens a fair bit with vista and the updates that it downloads from the Microsoft servers. After every critical update that Microsoft release, some Vista systems have been reported to think that the cd key is already in use and that the copy in question is illegal. This is caused by the automated system only allowing online activation to be done once a month by the same cd key (crap I know). A rather short term solution would be to choose to activate by automated telephone service and doing it manually over the phone with a representative.
Hope this has helped.
