Login to O365 fails with error "We received a bad request."

The Setup:

Two Web Application Proxy Servers and two AD FS 2.0 servers. Users are Office 365 users with a federated domain suffix so they must authenticate via AD FS.

The Story:

Initially, only a few users were having issues logging into Office 365. As the day wore on, more and more users were having issues until there was a full on outage. Both internal clients and external clients were affected. The clients were getting this error when trying to log into Office 365

 Sign In
Sorry, but we're having trouble signing you in.
We received a bad request.
Additional technical information:
Correlation ID: <ID>
Timestamp: <timestamp>
AADSTS50008: SAML token is invalid

The Hunt:

On the AD FS servers there were no errors being logged in the AD FS/Admin event logs. We were able to browse to the self test site:
https://<ADFS Server public FQDN>/adfs/ls/IdpInitiatedSignon.aspx

Using the test site, a user account using a machine located within the corporate network, was able to authenticate successfully against AD FS. But logging into O365 failed for the same users.

As we were switching remote desktop sessions, the administrator, from the corner of his eye, noticed a time skew between the AD FS server time and the WAP server time.  Upon further investigation, we found that the domain machines all had a time skew of about 20 minutes in the future of the actual time.

Since the WAPs are not joined to the domain, they are not using the DCs as the time source.

This time skew made perfect sense in relation to the error the clients were receiving.  The authentication token that AD FS was granting was not yet valid when it was received by O365 servers.

The Fix:

We set the time right on the DCs and rebooted the AD FS servers. After the AD FS servers were available again, with the correct time, users were able to log into Office 365 successfully.
:0)