No connectivity via Remote Desktop Services after Server reboot

In some cases, it might happen you are not able to connect to a server via Remote Desktop or Terminal Services shortly after a reboot.
In this case, restart the Firewall service from the local console and try again.