I used to run into that same issue with my Win2k server box. After a reboot, I had to log onto the machine from the physical terminal before I would be able to termserv into it. Unfortunately I have no idea what caused that or how to fix it since I just recently reloaded the machine to Win2k3 server and haven't had that problem since. =(
Just out of curiosity, is that machine connected to the network via copper or wifi?