I am working on setting up a hybrid environment so we can gradually migrate our users to O365 Exchange.

I have followed the Exchange Deployment Assistant steps and have also been referencing this checklist: http://technet.microsoft.com/en-us/library/gg576864.aspx

My on-premise user logon domain is not the same as our primary SMTP domain.

ADFS and Directory Sync have been configured and appear to be working fine.

When trying to establish a new Organization Relationship with O365, I get the following error:

[PS] C:\>Get-FederationInformation -DomainName 'federation.msa.com' -verbose | New-OrganizationRelationship -Name 'O
365 Relationship' -Enabled $true -FreeBusyAccessEnabled $true -FreeBusyAccessLevel 'LimitedDetails' -FreeBusyAccessScope
$null
VERBOSE: [13:45:28.507 GMT] Get-FederationInformation : Active Directory session settings for
'Get-FederationInformation' are: View Entire Forest: 'False', Default Scope: 'msa.com', Configuration Domain
Controller: 'AGP-AK01.msa.com', Preferred Global Catalog: 'agpdc01.msa.com', Preferred Domain Controllers: '{
agpdc01.msa.com }'
VERBOSE: [13:45:28.507 GMT] Get-FederationInformation : Runspace context: Executing user: msa.com/MSA/Contractors/cont1234, Executing user organization: , Current organization: , RBAC-enabled: Enabled.
VERBOSE: [13:45:28.507 GMT] Get-FederationInformation : Beginning processing &
VERBOSE: [13:45:28.648 GMT] Get-FederationInformation : Current ScopeSet is: { Recipient Read Scope: {{, }}, Recipient
Write Scopes: {{, }}, Configuration Read Scope: {{, }}, Configuration Write Scope(s): {{, }, }, Exclusive Recipient
Scope(s): {}, Exclusive Configuration Scope(s): {} }
VERBOSE: [13:45:28.648 GMT] Get-FederationInformation : Resolved current organization: .
VERBOSE: [13:45:28.648 GMT] Get-FederationInformation : Using the following trusted host names: *.outlook.com.
VERBOSE: [13:45:28.648 GMT] Get-FederationInformation : The discovery process returned the following results:
Type=Failure;Url=https://autodiscover.federation.msa.com/autodiscover/autodiscover.svc;Exception=Discovery for
domain federation.msa.com
failed.;Details=(Type=Failure;Url=https://autodiscover.federation.msa.com/autodiscover/autodiscover.svc;Exception=T
he remote name could not be resolved: 'autodiscover.federation.msa.com';);
Type=Failure;Url=https://federation.msa.com/autodiscover/autodiscover.svc;Exception=Discovery for domain
federation.msa.com
failed.;Details=(Type=Failure;Url=https://federation.msa.com/autodiscover/autodiscover.svc;Exception=The remote
name could not be resolved: 'federation.msa.com';);
Type=Failure;Url=http://autodiscover.federation.msa.com/autodiscover/autodiscover.xml;Exception=Discovery for
domain federation.msa.com
failed.;Details=(Type=Failure;Url=http://autodiscover.federation.msa.com/autodiscover/autodiscover.xml;Exception=Th
e remote name could not be resolved: 'autodiscover.federation.msa.com';);
Type=Failure;Url=http://federation.msa.com/autodiscover/autodiscover.xml;Exception=Discovery for domain
federation.msa.com
failed.;Details=(Type=Failure;Url=http://federation.msa.com/autodiscover/autodiscover.xml;Exception=The remote name
could not be resolved: 'federation.msa.com';);
.
Federation information could not be received from the external organization.
    + CategoryInfo          : NotSpecified: (:) [Get-FederationInformation], GetFederationInformationFailedException
    + FullyQualifiedErrorId : A93C5458,Microsoft.Exchange.Management.SystemConfigurationTasks.GetFederationInformation

VERBOSE: [13:45:28.663 GMT] Get-FederationInformation : Ending processing &

I have created the necessary DNS records so that autodiscover.federation.msa.com points to autodiscover.outlook.com.

My federated domains within O365 Admin Portal are msa.com, service.msa.com, and federation.msa.com.

My primary SMTP domain is agp.com, which is not a federated domain.  My SSL certificate used on the Exchange hybrid server is a wildcard for *.msa.com.

Any help would be appreciated.