Still no answer? I do have the same trouble on my iMac G5 PPC with 10.5.8: I just replaced the MOB and Time Machine insists to create a new bkup! Attempted with "tmutil" command but doesn't work on my OS...it is really impossible to tell the machine to learn the new address? I DON'T want to believe it!
Tks for any help