Ran into a strange issue recently where on-premises users could not see the free/busy information for test users I had migrated to Exchange Online. Exchange Online, on the other hand, had no problem seeing the free/busy of the on-premises users. I had just run the hybrid configuration wizard and it completed without incident. The environment had not been previously enabled for the Microsoft Federation Gateway so I let the wizard take care of that step as well.
When we tested the trust with the federation gateway we received the following error on Step 5 of 6: Requesting delegation token.
C:\> Test-FederationTrust -UserIdentity rsong@exchangeservergeek.com <...edited...> RunspaceId : e4e42cab-62f4-4d70-be15-69143b273823 Id : TokenRequest Type : Error Message : Failed to request delegation token. Error. Attempted to get delegation token, but token came back as null.
The token coming back as null seemed to be the key here. Unfortunately, the web seemed to lack any real way to fix the existing trust. We resolved to delete and recreate the trust with the federation gateway.
Recreating the Federation Trust
Warning: Before we get started with the process you will need access to external DNS zone. Recreating the trust voids the current TXT record that was used for domain validation.
To delete the federation trust navigate to the Organization > Sharing tabs in the Exchange Admin Center. Under the section titled Federation Trust click the Remove button. Click Yes to confirm.

Once the federation has been removed click Close. While still on the sharing tab click Enable.

The federation trust will be recreated. Click Close. Then click Modify.

On the Edit Sharing Domains window, click Browse. Select an accepted domain to use for the unique namespace of the federation trust. Under Step 2 click the Add () button to specify additional sharing domains. Add these new TXT records to your external DNS zone. Your old records will no longer be valid. Click Update to begin the domain validation process.

Confirm this resolved the issue by running the Test-FederationTrust cmdlet once more. This time all steps should pass and the token should be received. From here verify free/busy functionality with Office 365 mailboxes.
C:\> Test-FederationTrust -UserIdentity rsong@exchangeservergeek.com
<...edited...>
RunspaceId : e4e42cab-62f4-4d70-be15-69143b273823
Id : TokenValidation
Type : Success
Message : Requested delegation token is valid.
For other free/busy issues, I recommend checking out the Free/Busy Troubleshooter from Microsoft. This walks you through the troubleshooting process for many common errors.

Have you run into this error? What was your solution? Drop a comment below or join the conversation on Twitter @SuperTekBoy.
In this scenario you can simply run: Get-FederationTrust | select *Certificate*
If the TokenIssuerPrevCertificate is expired, run Get-FederationTrust | Set-Federationtrust –RefreshMetaData
This will refresh the Metadata and the issue will be resolved. The problem is limited to on-premises users who try to retrieve free/busy information for cloud mailboxes.
The background here is that there is a planned change to the Microsoft Federation Gateway (MFG). A certificate is being updated which means customers with a federation trust to the MFG must refresh their configuration so that they are aware of the new certificate. While this will affect Exchange hybrid deployments, it will also affect on-premises deployments that have a trust to the MFG.
Exchange 2013 SP1 systems installed onto Windows Server 2012 will automatically update themselves, but previous versions of Exchange will not. The same is true for Exchange 2013 installed onto Windows Server 2008 R2. Either you do this manually or create a scheduled task to periodically do this work for you. The steps to create the scheduled task are in the link to the planned change.