Verify Inheritence is enabled for the user in the Advanced Security tab of Active Directory Users and Computers. Admin accounts will have inheritence disabled once per hour dur to AdminSDHolder rules in AD, and without Inheritence Exchange 2010 cannot create the mobile device container under the user object to esetablish the partnership.
hat tip
Brian Day, Overall Exchange & AD Geek
MCSA 2000/2003, CCNA
MCITP: Enterprise Messaging Administrator 2010