Windows UPDATE "We couldn't connect to the update service. We'll try again later, or you can check now. If it still doesn't work, make sure you're connected to the Internet."

Also in UK & with BT.

I've just used the "change default DNS" solution (I used the google DNS: 8.8.8.8 & 8.8.4.4, but others available), mentioned elsewhere on the internet, it worked for me (on two devices). Now changed back to original settings (i.e. using ISP default DNS) and still working (on both).  Didn't even need to reboot, just changed the settings, triggered an update successfully, then restored the settings.

Such a pity Microsoft haven't tried a little harder to keep users informed.

Just to confirm, the method I used did work exactly as described. DNS name resolution query result is being cached so when you revert back to the original setting it will continue to work, but only while the (working) DNS name resolution query result remains cached, once it has aged *(sorry, don't know how long that takes)*and is cleared from the cache, the issue returns. So you either need to keep with the non-default settings until the problem is eventually resolved (one assumes, but who knows when) or be prepared to switch between default DNS and overridden DNS settings when you want to force an update.

As updates on the eventual resolution of this problem are not very forthcoming (at least not without having to hunt around for them) it becomes a matter of deciding for yourself which is option works best for you or rather that you find least frustrating.

Ok, so I am a BT Client. I have just built a new PC for a client and encountered this issue. I reinstalled just in case, the same issue. I used an older 1803 build media, same problem. Then a came across this thread. I set up my mobile as a mobile hotspot via my 3 network connection and bam all the updates came down.

I tried tethering to TalkTalk mobile last night; to no effect. Went back to BT hub and my laptop ( wifi connection ) seemed to access the Update Server, but the Desktop didn't ( Ethernet connection...... why??!! ). Desktop still doesn't and now nor does the laptop, again!!!!!!! I'm doing no more......... The machines work; I'll just monitor the situation day by day, as it's obviously a very external fault.

Ian

How can this be a BT problem when this thread seems to indicate that it is worldwide and I thought that BT was only in the UK.

This is not only a BT issue. It seems to be mist ISP in the UK. 

Regards 

Infinidim

Ian

How can this be a BT problem when this thread seems to indicate that it is worldwide and I thought that BT was only in the UK.

It has been identified with BT and Comcast mostly. I am on Comcast and my problem has been resolved. It is not likely a MS problem exclusively. Given the solution to change the DNS to another server, it is more likely a DNS problem related to specific providers. It will get resolved.