I've see this type behavior a couple times in the past, but I don't have any great solution. If it's like what I've seen it's not BIOS related - it's something funked up in the system software.
I suggest you go to a virtual console <ctrl>+<alt>+<f3> and login as root, and try to watch the shutdown from there. You can get back to the gui console with <ctrl>+<alt>+<f1> or similar.
One issue Ive seen is that when a user logs-out from the gui console, some processes remain and these can cause the shutdown to hang. So logout of the gui con and then from the virtual con do a 'ps -aefl' and look for processes that belong to the users.
IIRC back in the FC8 days shutdown sent signals to init and then the iniitab has some entry to actually kick the power. You may want to trace that out.