My preferred solution to this problem uses samba. There is a modification to the rpc client that issues the same remote shutdown that the MS version shutdown.exe (located on the resource kit) does.
Last I checked, it wasn't located in the regular samba source. You had to get the latest HEAD release. I don't use any of the other HEAD code for production level systems, but the rpcclient seems to be pretty stable for just issuing shutdown commands (just build rpcclient).
http://samba.org/samba/cvs.html
Thanks,
Jon