Hi,
It appears from the error that problem is related with insufficient permissions of the logon account used to backup Exchange mailboxes and public folders.
Following steps will be useful to isolate and resolve this issue:
1) On target(Exchange) system, create a new user. Make newly created user a member of Domain Admin group.
2) Create a mailbox for newly created user. Send an email to newly created mailbox from different mailbox.
3) Start Exchange system manager, by right clicking the organization start "Delegate control" wizard and grant new user "Exchange Full Administrator" rights.
4) Start Backup Exec, create a Logon account with same username and password as that of newly created mailbox enabled user. Make sure that the logon account is common logon account. To accomplish this, follow the steps given below:
-Start Backup Exec
-Select Tools > Wizards > Logon account wizard -Add new logon account, type in the credential for the new account.
-Make this account a common logon account.
-Complete the wizard.
5) Create a new backup job while connecting to Exchange mailboxes and select newly created user logon account.
6) Perform backup and verify the results.