clean-mailboxdatabase error : unable to sync mailboxes with DS

Are you sure about the permissions? Maybe you can try this one step by step?

http://support.microsoft.com/kb/960147/en-us

Cause

In Exchange Server 2003, the database cleanup agent can be run by any regular Exchange Full Administrator. This behavior is changed in Exchange Server 2007. When you run the clean-mailboxdatabase cmdlet in Exchange Server 2007, you must have Organization Administrator permissions. This is true unless you have granted the account or the group in question the minimum permissions set, as described in the "Resolution" section.

Resolution

To resolve this issue, use the Exchange Management Shell to add the minimum permissions set. To do this, follow these steps:

1. Open the Exchange Management Shell.
2. At the command prompt, run the following commands

Add-ADPermission –Identity “Exchange Administrative Group (FYDIBOHF23SPDLT)” –User –AccessRights extendedright –ExtendedRights “Administer information store", "View information store status"

Add-ADPermission –Identity “Exchange Administrative Group (FYDIBOHF23SPDLT)” –User –AccessRights GenericRead

To make these commands work, you must also use the Exchange Management Console (EMC) to make your account or group the Exchange Server administrator on the server. To do this, follow these steps:

1. Start EMC, right-click Organization Configuration, and then click Add Exchange Administrator.
2. Click Browse to select the account or group that you want to add, and then click OK.
3. Select the Exchange Server Administrator role option, and then click +Add.
4. Select the servers on which you want to add permission to the account or group, and then click OK 5. Click **Add, and then click** Finish.

Note To fully administer the Exchange server, manually add the user or group to the built-in local administrator’s group on the server.