Michael,

Sounds like name resolution problems to me. "Outside" connections rely on their own DNS, internally you have to handle properly yourself. How are your VNC/RDP connections set up? Server name or IP address? Any recent changes in your network? What do simple PINGs against the server show? What are these services that are failing?