check to see if they are using the same DNS servers as the machines it is working fine on.
ipconfig /all
Make note of the DNS servers being used. While you are out there in command prompt land, flush the DNS cache for fun with: ipconfig /flushdns
I would also check to see if they are resolving names properly with:
nslookup
www.somedomainname.com