When creating a Hybrid Configuration with Exchange 2010 and Office 365, the creation is successful:

Set-HybridConfiguration
Completed

Exchange Management Shell command completed:
Set-HybridConfiguration -Features 'MoveMailbox','OnlineArchive','FreeBusy','Mailtips','MessageTracking','OwaRedirection','SecureMail' -Domains 'domain.com' -ClientAccessServers 'SERVER' -TransportServers 'SERVER' -ExternalIPAddresses '192.168.1.1/32' -OnPremisesSmartHost 'remote.demo365.info' -SecureMailCertificateThumbprint '1FCB...'

Elapsed Time: 00:00:06

But Updating the Hybrid Configuration fails:

Update-HybridConfiguration
Failed

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. 

Operation is not valid due to the current state of the object.
   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 C:\Program Files\Microsoft\Exchange Server\V14\Logging\Update-HybridConfiguration\HybridConfiguration_5_11_2014_...log.

Exchange Management Shell command attempted:
Update-HybridConfiguration -OnPremisesCredentials 'System.Management.Automation.PSCredential' -TenantCredentials 'System.Management.Automation.PSCredential'

Elapsed Time: 00:00:45

Further detail can be seen in the log file:

[5/11/2014 4:53:24] INFO:Running command: Get-FederationInformation -DomainName 'demaincom.mail.onmicrosoft.com' -BypassAdditionalDomainValidation 'True'
[5/11/2014 4:53:24] INFO:Cmdlet: Get-FederationInformation --Start Time: 11/05/2014 12:53:24 PM.
[5/11/2014 4:53:49] INFO:Cmdlet: Get-FederationInformation --End Time: 11/05/2014 12:53:49 PM.
[5/11/2014 4:53:49] INFO:Cmdlet: Get-FederationInformation --Processing Time: 25896.166.
[5/11/2014 4:53:49] INFO:Disconnected from On-Premises session
[5/11/2014 4:53:50] INFO:Disconnected from Tenant session
[5/11/2014 4:53:50] 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. 

Operation is not valid due to the current state of the object.
   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 C:\Program Files\Microsoft\Exchange Server\V14\Logging\Update-HybridConfiguration\HybridConfiguration_5_11_2014_....log.

In adddition, the following error is seen when getting Federation information:

[PS] C:\>Get-FederationInformation -domain domain.com
WARNING: An unexpected error has occurred and a Watson dump is being generated: Operation is not valid due to the
current state of the object.
Operation is not valid due to the current state of the object.
    + CategoryInfo          : NotSpecified: (:) [Get-FederationInformation], InvalidOperationException
    + FullyQualifiedErrorId : System.InvalidOperationException,Microsoft.Exchange.Management.SystemConfigurationTasks.
   GetFederationInformation
    + PSComputerName        : server.domain.local

Testing the Federation Trust with the mailbox alias of a user reveals a certificate error:

[PS] C:\>Test-FederationTrust -UserIdentity USERALIAS

...

RunspaceId : 5de276bb-...
Id         : OrganizationCertificate
Type       : Error
Message    : Certificate referenced by property OrgPrivCertificate in the FederationTrust object is expired.

Find the Federation certificate:

[PS] C:\>Test-FederationTrustCertificate

RunspaceId : 5de276bb-...
Site       : domain.local/Configuration/Sites/Default-First-Site-Name
Server     : SERVER
State      : Installed
Thumbprint : 9DA5...

Get the details of the certificate:

[PS] C:\>Get-ExchangeCertificate -Thumbprint 9DA5... |fl

AccessRules        : {System.Security.AccessControl.CryptoKeyAccessRule, System.Security.AccessControl.CryptoKeyAccessR
                     ule, System.Security.AccessControl.CryptoKeyAccessRule}
CertificateDomains : {Federation}
HasPrivateKey      : True
IsSelfSigned       : True
Issuer             : CN=Federation
NotAfter           : 11/05/2019 10:33:35 AM
NotBefore          : 11/05/2014 10:33:35 AM
PublicKeySize      : 2048
RootCAType         : None
SerialNumber       : 36B2...
Services           : SMTP, Federation
Status             : Valid
Subject            : CN=Federation
Thumbprint         : 9DA5...

The issue is the certificate NotBefore time is issued with the current time in the Exchange server time zone. If this time zone is ahead of the time zone of the MicrosoftOnline Federation Trust servers, PDT (UTC -7), the certificate will not be valid until it is the NotBefore time in the PDT timezone.

The resolution is to wait until the NotBefore time in UTC -7.

When the following command completes successfully, the trust is valid:

[PS] C:\>Get-FederationInformation -DomainName domain.com

RunspaceId            : 5de276bb-...
TargetApplicationUri  : outlook.com
DomainNames           : {domaincom.onmicrosoft.com, domain.com, domaincom.mail.onmicrosoft.com}
TargetAutodiscoverEpr : https://pod....outlook.com/autodiscover/autodiscover.svc/WSSecurity
TokenIssuerUris       : {urn:federation:MicrosoftOnline}
IsValid               : True

Further information, including certificate expiry times are available with the following PowerShell command:

[PS] C:\>Get-FederationTrust |fl

This error can be avoided by creating a new federation trust in advance. From the Exchange Management Console:

- Select Microsoft Exchange On-Premises | Organization Configuration | Federation Trust tab
- Click New Federation Trust from the Action pane
- Click New

The certificate will still take the time delay, but this task can be done in advance.

Error message when you run the Get-FederationInformation cmdlet in Office 365: "An unexpected error has occurred and a Watson dump is being generated"
http://support.microsoft.com/kb/2710846

Manage Federation
http://technet.microsoft.com/en-us/library/dd876922.aspx