I needed to make a change to our Hybrid configuration when the following issue was encountered: Subtask CheckPrereqs execution failed: Check Tenant Prerequisites

After multiple attempts to run this and troubleshooting. I find out that the issue was caused by recent changes to Exchange Online.

The first KB informed me to remove an invalid certificate
KB2772596 – http://support.microsoft.com/kb/2772596

The issue still existed after after the removal, I later found the following: KB2988229 – http://support.microsoft.com/kb/2988229

Its time to run a cumulative update (CU). In my case I will need to be at Cumulative Update 5 for Exchange Server 2013 (KB2936880)

If you are unsure what version of exchange you are currently running you can use the following Exchange Powershell Command:

Get-ExchangeServer | Format-List Name, Edition, AdminDisplayVersion

Here is a table for reference below

Product name Release date Build number
Exchange Server 2013 CU5 May 27, 2014 15.00.0913.022
Exchange Server 2013 SP1 February 25, 2014 15.00.0847.032
Exchange Server 2013 CU3 November 25, 2013 15.00.0775.038
Exchange Server 2013 CU2 July 9, 2013 15.00.0712.024
Exchange Server 2013 CU1 April 2, 2013 15.00.0620.029
(RTM) Exchange Server 2013 December 3, 2012 15.00.0516.032