I swear, so much Microsoft installation / updating is:

Follow instructions…google error message…apply fix…google next error message…apply fix…google next error…etc…

The quick answer is: you need a wildcard certificate on your local exchange server to successfully setup the hybrid configuration.

You also need autodiscover.yourdomain.com setup and pointing to your server. Although the SRV method works for outlook, you can’t use a SRV record pointed to your mailserver’s acutal FQDN/Cert name to setup the hybrid config.

Symptoms are a failure setting up the hybrid configuration and log file entries like this:

ERROR:Updating hybrid configuration failed with error ‘Subtask Configure execution failed: Creating Organization Relationships.
Execution of the Get-FederationInformation cmdlet had thrown an exception. This may indicate invalid parameters in your Hybrid Configuration settings.

The method or operation is not implemented.
at System.Management.Automation.PowerShell.CoreInvoke[TOutput](IEnumerable input, PSDataCollection`1 output, PSInvocationSettings settings)
at System.Management.Automation.PowerShell.Invoke(IEnumerable input, PSInvocationSettings settings)
at System.Management.Automation.PowerShell.Invoke()
at Microsoft.Exchange.Management.Hybrid.RemotePowershellSession.RunCommand(String cmdlet, Dictionary`2 parameters, Boolean ignoreNotFoundErrors)
‘.

Additional troubleshooting information is available in the Update-HybridConfiguration log file located at E:\Exchange\Logging\Update-HybridConfiguration\HybridConfiguration_5_5_2015_2_29_19_635663897597564496.log.

And if you run Get-FederationInformation yourself you get an error like:

Federation information could not be received from the external organization.
+ CategoryInfo : NotSpecified: (:) [Get-FederationInformation], GetFederationInformationFailedException
+ FullyQualifiedErrorId : AB43F836,Microsoft.Exchange.Management.SystemConfigurationTasks.GetFederationInformation

So,

  1. Purchase a new wildcard exchange certificate for your domain and install
  2. Create the autodiscover.yourdomain.com A record in DNS
  3. Run the hybrid configuration again

PS

I’ve got an old hybrid setup that I let the wildcard certificate expire on and the hybrid configuration still works. Mail still flows, everything syncs and I can move mailboxes back and forth. So apparently you only need this certificate for the initial setup.