Sudden login failure on RDS server on Windows 2012

So, my knowledge on Remote desktop services is not so good, but I managed to get it up and running last year, it's been working just fine for eight months. Now today no Remote desktop users can login. Console sessions are working fine though. I checked and the licensing is okay, no errors. But users trying to login are logged in the security log such:

EVENT ID: 4625

Log Name: Security

Source: Microsoft-Windows-Security-Auditing

Date: xxxxxxxx

Event ID: 4625

Task Category: Logon

Level: Information

Keywords: Audit Failure

User: N/A

Computer: xxxxxxxxx

Description:

An account failed to log on.

Subject:

Security ID:                 NULL SID

Account Name:                      -

Account Domain:                            -

Logon ID:                            0x0

Logon Type: 3

........

To narrow it down I followed this tip to get logging running in the netlogon.log-file https://social.technet.microsoft.com/Forums/windowsserver/en-US/1001bb80-c490-4ec6-828a-9090588c570c/cannot-remote-desktop-into-windows-2008-server-eventid-4625?forum=winserverTS

My log shows the following:

03/11 22:38:44 [LOGON] [3000] SamLogon: Network logon of domain\user from client Entered

03/11 22:38:44 [CRITICAL] [3000] NlPrintRpcDebug: Couldn't get EEInfo for I_NetLogonSamLogonEx: 1761 (may be legitimate for 0xc000006d)

03/11 22:38:44 [LOGON] [3000] SamLogon: Network logon of domain\user from client Returns 0xC000006D

When searching on the [CRITICAL] part of the above log it looks like it has to do with the wrong DC is answering or something. We used to have a BDC but it is gone since long. I can't figure it out, Any suggestions?

Try to check if DC's and user machines has correctly synchronized time. If so, check your RDP setting and try to disable NTLM authentication. Another thing can be that some profiles are broken (because of some migration when SID's are gone), did you tried create new profile and connect to RDP with sufficient privileges to RDP? Last thing it can do this problem is with bad configured DNS servers on workstations and DC's.