I connected my Time Machine drive and immediately noticed a problem. Time Machine could not see any of my previous backups. When I browse the drive using Finder, I see them, but not with Time Machine. Turns out that Time Machine is closely coupled with your MAC address in 10.5.8 (not so in 10.6 Apple told me, so you 10.6-ers will not face this issue). Anyway, new logic board = new MAC address = unhappy Time Machine.
There is supposedly a fix that involves resetting the attributes of a plist file and renaming a hidden file in Time Machine. This method is detailed on the MAC OS X Hints website. The Apple tech told me that Apple engineers say this fix should work, but he has never had success personally. One little typo and it won't work.
I followed the directions to a "t," and it did not work for me. I was very careful about the spaces in my Time Machine backup disk name, but something still went wrong. Anyway, the old backups are still there, I just still cannot see them with Time Machine. Although now when I follow the Mac OS X Hints tips for finding the mac address associated with Time Machine, it shows the correct one.
Apple's suggestion, assuming you are not missing any major files on your system: Abandon your old backups and start fresh with Time Machine. Either that or update to 10.6 (which for me would involve purchasing a new version of Matlab, so no thank you).
Looks like I'll be starting over with Time Machine tonight, *sigh*.