I've had a similar thing happen recently. I've modded around 10 Xboxs for use on XBL so far without a problem. Within the last 2 weeks I have done 2 Xboxs and both were banned. The story behind both of them are nearly identical so I"ll just talk about one.
The xbox had been on live before I modded it. I installed the Xecuter 3 chip, swapped out the hdd for a 250gig, used a virgin eeprom in config magic and went about loading all the software like usual. After that I have a XBL test account to make sure it works. Both boxes were able to play Halo 2 online and download all the updates. So when I give the boxes back to their owners, one of them went to account recovery and got the "your hardware or software may have been modified" message and the other went to new account and while he was troubleshooting his connection he got the same message.
I know that live block was enabled, the harddrives were locked, and the new eeprom was good ( or else I could not have connected to live the first time).
All in all, this sucks