Hi -
A couple of things I can think of:
1. You didn't mention your Exchange version. Exchange 2000 or 2003 you can move the mailbox without additional steps. With Exchange 5.5, you need to run the Unity Bulk Logout utility to logout of the mailboxes and depending upon the number moved, run the Exchange 5.5 Optimizer - http://www.cisco.com/en/US/customer/products/sw/voicesw/ps2237/products_maintenance_guide_chapter09186a008044380f.html#wp1068342
2. If you are moving the mailboxes to new information stores, make sure you have run the Unity permissions wizard to grant the necessary permissions to the unitymessagestore service account, otherwise your users will not be able to access voicemail.
Regards,
Ginger
