Recalculating Active Sync Partnership
There is the possibility that even though users have devices synchronizing with their mailbox, that the HasActiveSyncPartnership attribute is not set. This Microsoft KB article provides further details:
In a nutshell you must run the following command to correct all mailboxes in Exchange.
Get-CASMailbox * -RecalculateHasActiveSyncDevicePartnership
Advise customer to check that their data is incorrect and to follow the KB article.