Can you access the server for other services ie mail and file sharing from these problem machines?
Are you using the server for DNS resolution and if so is it set correctly on these machines?
If you use the IP address of the server have you included it in your advanced settings under proxy setup (assuming you use IE and assuming you use the Proxy)
Regards Duncan