Remove ActiveSyncDevice Fails after restore user in Active Directory

The other day i had an issue at customer site that complain about two ActiveSync issues:

1. User cannot sync with new device.
2. Administrator cannot remove Active Sync device from user.

Both issues came from the same user, that was restored from backup couple of days before.
First issue was fixed by adding inheritance permissions for the object in Active Directory Users and Computers and in ADSI Edit. from some reason the backup software didn't set this automatically.