An object with the same proxy address already exists in Windows Azure Active Directory but is of an incompatible object type (object classes: contact, group, or user). Correct this issue in the local directory services or in Windows Azure Active Directory and try again.
In an Office 365 environment where DirSync is enabled and inbound mail flow from the Internet comes on-premise before being forwarded to Office 365, this error happens when a mailbox is created in Office 365 (as a non Federated mailbox) instead of on-premise with the new-remotemailbox command. This command create a local object with a remoteroutingaddress attribute to forward the email to the tenant domain.
To work-around the issue you can create a local contact object to forward email to the remote domain but this will cause DirSync errors like the one above.
To solve the problem, delete the on-premise contact objects and run the following command:
new-RemoteMailbox -Name "John Doe" -RemoteRoutingAddress firstname.lastname@example.org
You will be prompted to enter a password and a UserPrincpalName ex: email@example.com
This command attempts to convert the Online Identity to a federated Identity, but fails. That is okay, that is part of the process.
The next step is to launch Exchange Management Console and modify the remote routing address to firstname.lastname@example.org
Then run DirSync.
Finally, in an Online Services Powershell command change the UserPrincpalName as follows
DirSync one last time, and that will eliminate the errors and properly create the on-premise object to properly route mail from on-premise to Office 365.