I am having a similar problem. But first, i'll make my setup clear. I had a retail xbox that had been on Live before. Then, i got my box modded, and installed a brand new hard drive. I am fully aware of the marriage theory, and so i did NOT connect to Live after i got my mod (I know this for sure, because i've had my network cable unplugged since i got the mod). So, in order to get back on Live, i bought a virgin eeprom and installed it using configmagic (i also know that the new eeprom flashed ok). Anyways, my xbl info is nonexistent, since i have a new hd. The only options are to register a new account, or account recovery. so, i go into account recovery, and it says "Xbox Live service not found". When i troubleshoot it, this is what happens:
Cables connected: OK
IP resolved: OK
DNS resolved: OK
Xbox Live not found
I have seen a few other posts with other people having this problem, all after flashing a new eeprom. However, nobody answered any of those posts. I thought i saw something about the fact that a new eeprom would change the MAC address of the xbox. If this is true, how can i fix that problem? (I didnt back up my original eeprom, so i dont know my old mac address)