Let's be honest - every now and then SharePoint lies to us.
Case in point - I was working with my friend Nidhish today, getting SAML working on a SharePoint site. We started out be getting a strange HTTP 500 error when we hit the site. That in and of itself is unusual in my experience. So to try and understand the issue better we cracked open the ULS logs and found this error: "The issuer of the token is not a trusted issuer." Now having set up SAML in SharePoint approximately 3,492,234 times, I was fairly confident that we had configured the certificates correctly. Nonetheless, we then spent a fair amount of time looking at the certificates we had registered with the SPTrustedRootAuthority, comparing certificate thumbprints, double-checking the certificates in ADFS, recycling services and boxes etc. Just made absolutely no sense at all because every aspect of the certificate configuration appeared to be correct.
Finally I decided to review all of the relying party settings in ADFS again, and that's where I found the "real" problem. Turns out the WS-Fed endpoint for the relying party was mistakenly set to "https://foo", instead of "https://foo/_trust". All the certificates were in fact correct, but the request was getting redirected to the root instead of the _trust directory. Once the WS-Fed endpoint was updated everything began working. Just a little nugget that you may find helpful sometime.