There are a few other things that could cause this. Is the gateway configured to send to the MQM? Is the IP of the MQM correct on the gateway?
I typically like to telnet from the command line of the gateway to the MQM over port 80 to see if I can connect and confirm that the firewall isn't blocking the traffic.
Another situation that occurs from time to time is the windows firewall on the MQM itself can block port 80. Either make sure that port 80 is open on the windows firewall or disable it completely.
Beyond that, I would recommend to call in to support so we can assist further. Hope this helps. Thanks.