I've had a G4 that passed the Apple Hardware Test while having continuous kernel panics and trouble starting up. It turned out to be the logic board itself, a problem that Hardware Test was clearly unable to detect.
My first guesses are always
1. Bad memory
2. Bad logic board
3. USB or other device bus panic kernel
#2 is hard to eliminate. Re: #3: Do you have any external devices that might be troubling either the USB or FireWire buses?
There's a
discussion on the Apple forums with useful kernel panic-related links.