Internet access issue

Ok, so as I understand this....

Your local server (Mandriva) is acting as a proxy server, is this correct?

What proxy daemon are you running? What version?

Did you check the configuration of your proxy server software?

It also sounds like all of the Linux-based PCs cannot access the URL while the Windows-based PCs can, correct?

On the Windows-based PCs, are you using Firefox or Internet Explorer?

What version of Firefox are you using on the Linux machines?

What version of Firefox are you using on the Windows machines?

Do you have any Firefox extensions installed? On the Linux machines? On the Windows machines?

Do the Linux and Windows machines have the exact same Firefox extensions installed?

Are all Firefox extensions on all machines at the same version?

Did you modify netfilters via iptables on the Linux machines?

Did you modify the host file on the Linux machines? On the Windows machines?

Did you modify hosts.allow and/or hosts.deny on the Linux machines?

From the Linux machines, can you traceroute to the url's (IPs)?

It is only this one URL that the Linux cannot access, correct?

Is the url to somewhere local on your network? or is ot to somewhere on the Internet? aka is it an internal or an external url?)

We need more information to properly troubleshoot the issue. A good methodology to follow when it comes to troubleshooting is to follow the OSI Model by starting at Layer 1 and working your way through it until you reach Layer 7. No point in troubleshooting (Layer 4 - Transport) if the cable isn't plugged in. (Layer 1 - Physical)

Good answer from Ron, one thing he didn't mention is "ping".

See if you can ping the target machine from the client. If you can't, no point in contemplating what is happening at a high layer.