I have a problem where email messages are going into the root of the mailbox and backup cannot access them. I have a screenshot of the problem and I can email that to anyone you can help.
Usally this problem occurs if Logon account used to backup the Exchnage Mailboxes has insufficient permission.
Following article may help you resolving the issue. http://support.veritas.com/docs/256313
If this does not help then ensure that logon account used to backup the mailboxes has unique mailbox created on exchnage server and has Full Exchange Administrator permission.
If you can give the exact error message then we can further troubleshoot the issue.