This error appears when you attempt to authenticate with Office 365 using AD FS 3.0 – but only sometimes, and often it was working fine and then it starts!
I’ve found this error is due to two things, though there are other reasons. The full list of issues is at http://blogs.technet.com/b/applicationproxyblog/archive/2014/05/28/understanding-and-fixing-proxy-trust-ctl-issues-with-ad-fs-2012-r2-and-web-application-proxy.aspx.
I found that this occured if the WAP servers and the ADFS servers where at different timezones (not just times)
And I found that if the domain schema level is no 2012 R2 then you need to run the script included to copy settings between the ADFS servers. Certificates expire every 20 days, or when they are manually changed, so this script needs running by hand at or before these regular changes.
The second of these two issues though has been fixed in the June 2014 update for Windows Server 2012 R2. The fix is documented in http://support.microsoft.com/kb/2964735 and the update (the June 2014 update) is at http://support.microsoft.com/kb/2962409