My Mac Mini system (1.5 GHz G4) suddenly refused to startup: it got stuck on the gray screen with the Apple logo in the middle and the spinning progress meter at the bottom.  I let it sit there for 30-60 minutes a few times, and overnight for about 8 hours another time, but it never got past that screen.  From other systems, I was unable to SSH into the Mini, so it was stuck somewhere before the network connection could be brought up.

I was able to boot into single-user mode by pressing Command-s (actually Win-s on my keyboard) at the startup sound, at which point I ran fsck, which claimed to fix a couple of minor-looking issues, but the system still would not start up fully.  Rebooting into single-user mode again and attempting to run "sh /etc/rc" as the screen suggested, I got the following errors:

[...]/IOKit ... Reason: image not found
couldn’t find root user ... sleeping and trying again

Those errors just repeated over and over on the screen.

I booted from my OS X installation DVD (by rebooting with the DVD in the drive and pressing c at the startup sound) and ran its "Repair Disk" and "Repair Permissions" tools, neither of which solved the problem.

I disconnected everything except for the keyboard, mouse, and monitor, but it didn’t help.

I booted into single-user mode and recreated the netinfo database, but that didn’t help.

I reset the PRAM by holding Command, Option, p, and r (really Win, Alt, p, and r) at startup, but that didn’t help.

I tried to boot into safe mode (by holding the shift key during boot) but the system still never got past the gray Apple-logo screen.

Finally I booted from the OS X installation DVD and did an "Archive and Install" which got the system working again.  This didn’t actually auto-import my users, settings, files, etc (the option was grayed-out), but it did preserve all the files from the previous installation (including all user files) in a new top-level directory called "Previous Systems."  So it was basically a new, clean installation, but I still had all my files.