Hi -
If you are installing 4.1, the Exchange permissions are needed at the Exchange Administrative group level. Versions less than 4.1 required permissions at the Exchange Organization level. See this link - http://www.cisco.com/en/US/customer/products/sw/voicesw/ps2237/products_administration_guide_chapter09186a0080531bb0.html#wp1049373
Also, the messagestore service account is granted the following permissions on the Exchange 2003 and/or Exchange 2000 mailstores that are selected in Permissions wizard:
Send-As
Receive-As
Administer Information Store
View Information Store Status
You should confirm these permissions were indeed successfully run by the Unity permissions wizard.
Ginger