Kyle and I just worked on this issue today (case #00824040). The issue came down to having multiple servers in amazon web services having the same server name. If you did a nslookup from the Veeam Provider Server, it responded with 3 various IP address, 1 correct, 2 incorrect. Once we changed the server names, the gateway was able to accept connections. Kyle mentioned towards the end of our call that he was going to update this case with his findings as well.