yes, time machine uses a disk-specific ID that is somehow based on or compared to the MAC adress of your computer. google once told me this, but I cannot find the page right now.

when you check your startup log, you'll probably see that there is an error message that "no network card can be found" or alike. I guess this is the same issue.