Synchronization to Microsoft failing - WSUS SP2

[Jadus01]

I have a problem with WSUS SP2, where the synchronizations to Microsoft are
failing. The error is as follows:

WebException: Unable to connect to the remote server --->
System.Net.Sockets.SocketException: A connection attempt failed because the
connected party did not properly respond after a period of time, or
established connection failed because connected host has failed to respond
65.55.185.26:443
at System.Net.HttpWebRequest.GetRequestStream()
at System.Web.Services.Protocols.SoapHttpClientProtocol.Invoke(String
methodName, Object[] parameters)
at
Microsoft.UpdateServices.ServerSyncWebServices.ServerSync.ServerSyncProxy.GetAuthConfig()
at
Microsoft.UpdateServices.ServerSync.ServerSyncLib.InternetGetServerAuthConfig(ServerSyncProxy proxy, WebServiceCommunicationHelper webServiceHelper)
at
Microsoft.UpdateServices.ServerSync.ServerSyncLib.Authenticate(AuthorizationManager
authorizationManager, Boolean checkExpiration, ServerSyncProxy proxy, Cookie
cookie, WebServiceCommunicationHelper webServiceHelper)
at
Microsoft.UpdateServices.ServerSync.CatalogSyncAgentCore.SyncConfigUpdatesFromUSS()
at
Microsoft.UpdateServices.ServerSync.CatalogSyncAgentCore.ExecuteSyncProtocol(Boolean allowRedirect)

I have traced the day this started happening as the day we installed
Terminal Services Gateway on this server. I now know that TS is incompatible
with WSUS, so I have removed TS Gateway and the included options, however I
am still receiving the error.

Has anyone come across this, or know of a solution?