Exchange account used for synchronization must have rights to impersonate all users in the synchronization profile.
To configure impersonation for Microsoft Exchange Server 2013 Online use the following steps.
Login to https://outlook.office365.com
Go to Admin->Exchange
In the left pane choose permissions
admin roles links should be highlighted. Press + sign and add new Role ApplicationImpersonation for Synchronizer Exchange account. Press Save.

Redo Check All Logins test in the Profile Wizard of the synchronizer.