ADFS error duing SAML Service Provider Login

Based on suggestions from a Windows Admin, I did the following which resolved the issue.

1. Ensured W32Time service was using NTP (it wasn't)
2. Ensure all updates were installed (they were)
3. Ensure all services were running under a service account, not an domain controller account (they weren't)
4. After making sure ADFS was running under the service account, recreate the Service Provider

At this point, the error was only occurring for a subset of AD users. On those users, I reset their passwords, which then resolved the issue.

Although I am not entirely sure why this started happening or how these steps fixed it, my theory is that not using one service account to manage all of it led to files being written that couldn't be read in by processes running under a different account.

Hope this helps someone.

Update:

Another possible cause of the error is if you change the UPN in Active Directory to a string containing a space, this error shows up.

2nd Update:

Using a invalid domain can also cause this error.