Disk Utility cannot seem to complete the repair of...
I'm with the others in recommending Disk Warrior. I don't pretend to be any kind of expert but DW has saved my bacon a few times over the years.
I'd also recommend using DW's Scavenge function. Hold down your Option button when you click Rebuild to get to this feature.
My daughter once had a series of continually worsening problems on her G4 that culminated in a churning beachball for 24 hours followed by a hard shutdown. The DW Scavenge function sorted it out. That was about three years ago and it's worked fine since.
Finally, as if I needed more aggravation, starting up now seems to take about 6 minutes compared to about 1 minute previously, and shut down is also taking longer.
Do you have a device like an iPod attached? Twice I have experienced this lengthy startup problem and my iPod Nano was the source. The first time I thought "bad cable" and it was replaced, however it happened again, just the other day, with the new cable.
My startup was about 9.5 minutes but, when I unplugged the iPod, it was back to 30 seconds. The iPod can be plugged back in and will work, as the problem takes quite a while to develop.
In this recent case, the iPod itself got hung-up and needed a soft reset.
ryck