MS Proxy does include a SOCKS proxy. What kind of work do they need to do? If it is just web browsing, then just enable the proxy config on the browsers on the *nix boxes. If it is an application, then you will need SOCKS support to be able to gothrough the proxy server. Now, have you tried to ping an internet server from the *nix boxes? Can you ping the proxy box? Your question leaves out quite a bit of troubleshooting info, please include more detail for a better answer.
Thanks
Anthony Testa, MCSE
fataugie@rochester.rr.com