Group Policy was not being enforced when users logged in to our Terminal Services servers. Checking through the application event log I found the following error listed:

Event Type: Error
Event Source: Userenv
Event Category: None
Event ID: 1000
Date: 05/04/2007
Time: 16:53:44
User: NT AUTHORITYSYSTEM
Computer: SERVERNAME
Description:Windows cannot determine the user or computer name. Return value (1722).

This indicates some kind of DNS, WINS, NETBIOS issue so the first place was to head off to the DNS server and sure enought the problem was that the DNS server had stopped working when Active Directory was removed from the server. After  repointing the DNS settings to another valid DNS server all is well.