In the Windows Application Event Log, I found multiple Event ID 5586 entries - basically saying "The target principal name is incorrect".
After a few hours of searching, I found one solution here:
* Note that he doesn't indicate that you have to adsiedit.msc to get to the entry (a little headscratching to figure that out).
Some say it worked for them, but it definitely did not work for me.
For one, there were no MSSQLSvc entries. For two, removing the RestrictedKrbHost entries condition went from bad to worse (new error: Unable to login to untrusted domain). I restored the RestrictedKrbHost entries just fine so I tried adding the MSSQLSvc entries and got "Name is not unique".
The final one that worked for me was:
Step 1) Logged on the AD Server and opened adsiedit.msc (Run as administrator)
2) Right clicked on the SQL Server entry and clicked Refresh:
3) Opened AD Users & Computers, right clicked on the account running SQL Services and clicked Unlock Account:
Hat tip to David Murdoch's post *:
Note: his blog incorrectly says "Refresh" from Active Directory Users and Computers - you actually have to use adsiedit.msc.