It seems to have worked for me (at least the rebinding of my new MAC address). I didn't have a repair, but I did get a new MacBook Pro and cloned my system to my new machine. I'll update if/when it completes.

It only took about an hour for its first successful backup, and has kept my history intact (back to February 13th, 2008).

You don't even need to back up first to see how much history your re-paired Time Machine disk gives you. Simply start Time Machine after applying the above hint :-)

(by the way: until recently I did not know how brilliant Time Machine integrates with Apple Mail. Start Time Machine when Mail is active and presto: read emails, even from accounts you've completely deleted. Just back up more often than purging your deleted items...)