And then the box just disappears, without an error message or any other hint as to what might have gone wrong.
The interwebz abound with reports of this happening, and people asking how to fix it, and various solutions being offered that range from the complex to the hopelessly complex.
Luckily, every time I have encountered this problem, the solution for me was very simple: just wait and try again later. The remote computer is probably busy booting, or perhaps booting and installing updates.
Now, I will tell you a little secret: when something goes wrong, software can ALWAYS give a meaningful error message. If it does not, then someone, somewhere, is being either EVIL or INCOMPETENT.
If it could not find the server, it would have said that the server was not found.
If the server was not responding, it would have said that the server is not responding.
In this case, the server was actively refusing the connections, and someone at Microsoft was either so evil that they decided that in this specific case the software should not say anything, or, more likely, someone at Microsoft was so incompetent that they could not simply write their world-class software to give a meaningful error message in a very frequently occurring usage scenario.