When a federated user tried logging into Office 365 portal, the generic "We have received a bad request" error came up in the browser. The detailed information towards the bottom of the browser had a proper error.
A correlation id and timestamp of the error was displayed and the last line of the detailed information had the error below.
AADSTS5008 SAML token is invalid.
There were no ADFS errors to go by. A specific detail that got my attention was the timestamp displayed in the error. The time shown was not matching with what the user was seeing on his desktop.
After looking more into it, we nailed the problem. The issue was that the time throughout the AD domain was off by 7 minutes than the standard time. The PDC Emulator was not synching the time with a trusted external time source, but was using the CMOS clock. Go figure!
Since all machines across had the same time (even though different from the actual time), every other operation was working fine. The issue went away as soon as the AD time was brought in line with the actual time.