I'm not a Unix Geek, just a newly arrived newbie from the Classic Mac side.
I found the shutdown problem you described when setting up a headless Mac OS X server. Here's what I found works for me... Instead of just Shutdown, try
Shutdown -k +0
That will log out all users except the administrator (yourself) immediately. (if you want to give users time to logout, change the +0 to +5 for five minutes, or whatever.)
BUT, this command stops here - it doesn't actually shut down the machine. So now issue the halt or reboot command. These two commands issue the needed signals to running programs to gracefully exit, and then shutdown or restart the system.
See man halt for more info.
(Here's hoping I got this one right!)