I'm with most of you here... I think it's a PC-related issue and most likely is the whole MS Passport that's to blame.
I'm not saying MS's Passport system is bad, because it isn't, but I think this is a clear phishing case.
If a lot of people are having their accounts hijacked, the probability of it happening from people in-game soliciting personal information from gamers is impractical. At the same time, if it was an external hack into MS's database(s) and/or an internal leak of sensative database information, then surely we'd see a much larger stink than this. Also, the probability of a leak or a hack is highly unlikely.
This leaves the PC for the medium where these accounts were compromised.
As one guy on this thread has already stated, he himself was a victim of this at one point and swears it has nothing to do with his 360. He's probably right. It was probably from his PC.
To be honest, I've personally seen many fake MS Passport phishing pages, so the fact they exist is already widely known. Of course, I'd never fall for such ridiculous crap (and never do nor have), but at the same time I can see how less fortunate people could easilly buy into it.
All MS has to do is start sending messages either in email form and/or in XBL form to all users reminding them how to make sure a website is an official MS one, etc. Case closed.