Just out of curiosity - did you also reflash with a new EEPROM while you were installing the new hdd? The exact same thing happened to me. I was using a WD 120GB hdd for Live when for some reason it developed bad sectors and I was forced to upgrade to something else. My gamertag had NEVER been flagged/banned, and I signed on with Live after the 120 had been installed. When installing the 320GB drive (i copied the data on C and E from the old drive to the new and reflashed with a new EEPROM) I tried to access Live with the chip off. It worked. I logged into Live about 4 hrs later and got the famous Modded Console message, although I have no idea what from since my gamertag had never been banned/flagged. It seems in my case, MS somehow attached my gamertag to the eeprom and/or hdd serial #, which is contrary to the current knowledge of the Marriage Theory. ONce i got the Modded Console message I just said screw it and got yet another HDD, EEPROM and cancelled my Live acct. After installing the new-new hdd/eeprom I resubscribed to Live with a different subscription code and Gamertag. Everything has worked 100% since then.
I am curious to see if you also got banned the same way I did. If so, and if you are 100% certain you have never been flagged/banned before, it might indicate that MS is now associating Gamertags with eeproms/ hdd serials for a few ppl.