Have you also created a new Exchange account for the Operations user, and set that to be the default profile within Outlook, so when Outlook is opened that is the account that is viewed?
Backup Exec uses Outlook to access the mailboxes and backup their data, which if I'm right and your Outlook is still configured to use the administrators account would explain why it can't backup the mailboxes, but can backup the Information Store, since that is done direct with Exchange, rather than through Outlook.
On the good side though, while you can't currently restore an individual mailbox / e-mail, you have still got the disaster recovery situation in hand as long as the Information Store is being backed up.
Keith