The specified domain either does not exist or could not be contacted

First thing would be to check the eventlogs on the server and see if there is an error for RPD services.  Make sure that they are running on the server and not hung.

I would also check to make sure that the DNS resolves to the correct IP.  If that has changed then users would see this issue.  Also check to make sure that an update did not adjust the local firewall settings and block users.

Verify the DNS.
Do an Ipconfig /all to and make sure the DNS listed is the one that server the domain. Some time you may have a router that also assign IP and assign the wrong the dns. If that's the case disable the DHCP on the router and make sure the DHCP assign the proper DNS. If you have a DHCP server you can configure this on the scope options

Joshua: I don't see anything unusual related to RDP in the Event Viewer. The DNS resolves correctly back to the external IP here . Firewall is off.
infedonetwork: The router (Cisco ASA 5505) has dhcp disabled.

I doubt this is relavent but the DC is a VM running in Hyper-V. I also rebooted everything (host and all VM's)

VM should not make a difference.  Can you RPD to the terminal server via IP?

I definitely can hit the server. The problem is when trying to log in to the server it throws that message.

You can try this but I have the feeling your problem is on the DNS: https://support.microsoft.com/en-us/help/947022/the-netlogon-share-is-not-present-after-you-install-active-directory-domain-services-on-a-new-full-or-read-only-windows-server-2008-based-domain-controller
Each time I had to deal with the same problem as you have now it was eider the wrong DNS or wrong entry on the DNS
Do a nslookup and type the DC name and see if it resolve to the proper IP

Try this on the Domain Controller, Terminal server and the client PC
Reset DNS from CMD ipconfig /flushdns
Then try again

Flushed the DNS, didn't help.
I did see that there was no static IP set in dns on the TS to point to the DC so I corrected that. There were static IP's set but they were to outside IP to the ISP. The preferred  DNS IP now points to the IP of the DC. I tried to connect to the TS from the outside and got the same message.
I don't have any AD replication going as far as I know. This literally happened overnight.

Spoke too soon. It must have taken a little while to propagate. Setting the Primary DNS IP to point to the DC fixed it. Odd that this even has worked for all this time.
Thanks for all the help!