I have this Pentium 4 800 MHz running Xubuntu 8.04 (Fully updated as of 8-8-2008) that - when told to shutdown - does the shutdown stuff and then freezes in the shutdown graphic screen (you know, the same one you see when starting up).
Then I hear a click; I THINK the hard drive is shutting down. But the fans keep blowing and the screen keeps showing. Back when it was running XP, it did power off, so I know it's got the proper hardware for that.
Also, sometimes (looks random to me) when told to shutdown, it partially reboots, showing me a 'what to do next' screen. Also sometimes, it just goes back to the login manager, as if I restarted X by ctrl+alt+backspace. In both cases, I disipline the computer by switching the power (at the back of the computer) off, because if I wanted to play games I wouldn't tell it to shut down.
PS - I remember my P2 266MHz had the exact same problem a million years ago with Red Hat 5. It was fixed when I installed Xubuntu 6.