Is anyone logged interactively e.g. via VNC or an autologin? I've seen this occasionally when something hangs in the interactive session. Typically this happens after the VNC and TS servers have shutdown, so there's no way to get in and kick the server! These days I insist all my servers have a DRAC card (on an HP use the iLO card) so I can hard reset them remotely if I have to.
JR
Does this help:
http://support.microsoft.com/kb/930045
A way to test this would be to create a scheduled task to restart the server in (e.g.) 5 minutes then log out. That way there is not terminal servivce session active when the restart happens. If the restart now works normally the above may well be the reason.