We had an issue last week where the Data Stores on Exchange needed clearing out. At the same time we were unable to create new mailboxes, when we went through the wizard and the timer starts showing the new mailbox being created it wouldn't actually create the mailbox.
The time would just go on and on.
Also do you have any of this conditions: https://support.ca.com/cadocs/0/CA%20ARCserve%20%20Backup%2015-ENU/Bookshelf_Files/HTML/MS_Exch/index.htm?toc.htm?exchange_unable_to_create_the_user_account_create_the_mailbox_or_finalize_the_mailbox.htm ?
Do you have any error messages in event viewer or when you try to create the mailbox?