I say most likely the solution is not yours to give, as long as;
The Domain Name resolved to your IP Address (Name Server Problems), check by digging from outside of your networks.
Your server is reachable (network issues), check by doing traceroute also from outside of your network.
Your web server is listening correctly on the http port say 80 (configuration issues) for that specific domain, also you could check this by using services like browsrcamp.com.
If the problem is persistent and not only temporary, sad to say that probably you should advice the client to move to another hosting company or move to your server on different network.
If a lot of your client complaining about the same thing, you probably should move to a different network.