When installing OS upgrades, it is recommended to use the Disk Utilities app to do a "Repair Disk" and "Repair Permissions". For a clean install you only need to do this after the install, but for an upgrade the recommendation is to do it before and then after.
Boot from the installation disk, and use the Disk Utilities from there, as a Disk Repair cannot be run from the main drive.
That might clear up your problem. I have seen this on older machines before. I upgraded a PBG4 to a 300GB IDE drive. This had the Disk Utilities run on it, but it still did it. I put in down to the fact that it had a larger volume to search for bootable systems than before. I haven't heard any cries of help.
Having a TimeCapsule is good, at least your reasonably safe. I have a TimeCapsule too, great aren't they?