RDP in 2008 R2 domain no longer working - possible Kerberos issue

Everything was working fine and no changes were made. For no apparent reason, we can no longer RDP to any domain computers except for the domain controllers themselves. This includes Windows 7 clients and non-controller 2008 R2 servers. After entering the password, we immediately get the following error message:

"The logon attempt failed."

No other information and nothing of value in the event log of the target computer. The only hint as to what's wrong comes from examining the security log on one of the domain controllers, which shows the following Audit Failure (4769) after each login attempt:

A Kerberos service ticket was requested.

Account Information:
    Account Name:       <user>@<domain>
    Account Domain:     <domain>
    Logon GUID:     {00000000-0000-0000-0000-000000000000}

Service Information:
    Service Name:       <user>@<domain>
    Service ID:     NULL SID

Network Information:
    Client Address:     ::ffff:<ip>
    Client Port:        64170

Additional Information:
    Ticket Options:     0x40810000
    Ticket Encryption Type: 0xffffffff
    Failure Code:       0x1b
    Transited Services: -

This event is generated every time access is requested to a resource such as a computer or a Windows service.  The service name indicates the resource to which access was requested.

This event can be correlated with Windows logon events by comparing the Logon GUID fields in each event.  The logon event occurs on the machine that was accessed, which is often a different machine than the domain controller which issued the service ticket.

Ticket options, encryption types, and failure codes are defined in RFC 4120.

From my own searching, this seems to have something to do with SPNs. However, this is an area that I've never touched before. Any ideas on how to get RDP working again?

Already tried applying all Windows Updates and restarting the client, target, and domain controllers. No effect. Other services, such as file sharing, are unaffected.

Are you able to logon directly on the server with the account that leads to the error message?

Just to narrow down the problem you could try to disable Network Layer Authentication on one of your servers: Admintools -> Remote Desktop Session Configuration -> Security Layer: Set it to RDP