Many things could happen, in my case I have working everything fine for a NAT except SSL, that refuses to work no matter what I do, and using squid is not an option :/
A faulty NAT could lead to packet fragmentation, packet loss, etc. If the client is NAT'd by his home router, he could try putting his PC on the DMZ for test purposes, or connecting straight to the ISP modem/router/etc if it is the case.