Have you checked the client logs for any errors?
Have you reinstalled the client?
Have you modified the "Access this computer from the network" in GPO. If so you need the connection servers listed.
Worse case: Try a different user account logged into that workstation. If that works then you will probably want to blow away the users profile.
also try the below:
1- if you have more than one connection server , try to connect to each one my its name or IP
2- try to change the client ip address and try to change the network port
3- check windows logs for errors along with horizon client
Different users seem to give the same result so that's quite the relief. I can access everything from a different network just fine, so its really odd that it wouldn't work on his machine. He eventually got a proxy error but no one else has any problems with it.
Is it blocked by Firewall? is the other Horizon Server can be connected from this client?