The subject behavior can occur if the DNS server IP address is not properly configured on the client.
To fix the problem on the client:
1. Right-click My Network Places and press Properties.
2. Right-click Local Area Connection and press Properties.
3. Double-click Internet Protocol (TCP/IP).
4. Select the Use the following DNS server addresses radial button.
5. Type the proper DNS server address(es).
NOTE: An administrator may need to verify the DHCP scope that contains the correct DNS address(es).
You can use the Gpresult freeware to troubleshoot group policy issues. look for error 1789.