Are you sure that the server actually rebooted? W2k3 has a tendency to throw you out of the RDP session if you initiate a regular restart through it, not accept any new RDP connections, and continue to do whatever it did before without ever rebooting.
Check the event log remotely for event ID 6009 or 6005; if you don't find one at the time you wanted to reboot, then what I described above is your problem.
That can be fixed without another remote adminstration tool.
Start compmgmt.msc, right-click "My Computer", and connect to the remote machine. Right-click "Computer Management (RemoteServer)", and open Properties. Go to the Advanced tab, click the button in Start and Recovery, click the Shutdown button, choose "Reboot", and "Always force applications to close". Click OK, and the machine should reboot for real now.
Or try a simple
shutdown -m \\RemoteServer -f -r
(I've actually never tried tried the shutdown command, I'm just using the computer managament to check the event log, and then click my way through it ...)