I do not know, you connected the HDD to both your Macs (Firewire 800 or USB I guess), but one HDD cannot be connected physically to two computers that way.
Either you connect the HDD to one Mac and let that one Mac share that HDD to other Macs via your home network or you use a network HDD (NAS) to connect with two Macs or more to the same HDD.
That would explain, why the HDD did not show up on either Mac while being connected to both, but did show up, when one Mac was shut off. Time Machine has nothing to do with it.