You mentioned two different problems you've had with TimeMachine:
my machine failed and then was repaired, time machine could not recognize it.
the machine failed all together and I bought a new Mac -- Time machine was useless because it seems to be tied into one machine
Depending on what was repaired in that first instance TM very well might not recognize your machine for continuing to make backups and in the second case TimeMachine would certainly insisit on making a new backup set. But in both cases, had you attempted to restore your computer using the TM backup, it would have worked unless your TM backup itself had been damaged.
For reasons I won't go into, I frequently restore my computer with TM and I've experienced no failures. This includes setting up a brand new computer from a TM backup from my old computer and restoring a computer that required a new logic board - those are similar to your two reported problems.
Now I have had TM fail - but the failures have been during the backup phase, not restore. I've never had long term success backing up to a drive connected to my AirPort and in a couple of instances TM has informed me that the backup failed (to drives connected directly to my computer) and nothing I did could fix it other than erase the backup and start over.
I trust no single backup. I have TimeMachine running for every one of my computers. I also update a clone once a week using SuperDuper!. I have a two more SuperDuper! clones that we cycle between home and my wife's office so we always have an off-site backup that's no more than 1 week old. And I use DropBox as another repository of offsite data. (My sensitive data is kept in an encrypted disk image.) You might think this is overkill but I have experienced catastrophic data loss and don't intend to do so again. I also had the unfortunate experience of watching a former client go into bankruptcy when his office burned to the ground and his computer & only backup were destroyed.
