I've seen failing shutdowns on Fedora when some processes are hung on IO.
When you are at the black screen, try pressing Ctrl-Alt-F1 (or F2, ...).
It should bring up a command prompt, from which you can for instance check for hung processes (using the "ps" command).
If that works, you can use Ctrl-Alt-F7 to go back.
It's also possible that some of your "kill" scripts in /etc/rc.d (or etc/init.d) don't work like they should.
Basically, when you shutdown, those scripts are called, in a specific order (see "man chkconfig"), to shutdown
all services and stuff. If one of those hangs, your shutdown may be interrupted too.