Error message "Resouce Records (Host a) can't be found on authentication Server"

I manage a network with over 80 workstations and 4 servers. Recently I move 2 workstations from one location to another on the network. In most of the locations (where there are groups of 4-6 computers) frame relays are used to connect them to the network.

The 2 workstations that were moved are not connecting to the network now; before however they worked fine and were connecting to the network at thier previous location. The interesting thing is that I can ping the servers from the workstations but cannot ping the workstations from the server.

The workstations allow you to demote them from the domain but doesn't allow you to pormote them back to the domain. I have taken both workstation to my office and they have connected to the network there so the workstations them selves are ok. 

When trying to promote the workstation to the domain I receive the error message "A Domain Controller could not be reached on the specified domain" even though it can ping the server. The detailed view of the error says that the host (a) Resource record was not found. I tried using nslookup but it says the server is unknown and that the domain is unknown as well

Please help as to how I can fix this problem