I was having a similar problem during a migration of Exchange. When I had moved mailboxes, public folders, etc to a new server I edited my BackupExec selection list to start including the new server. Sure enough, when I clicked on the Mailbox Store and Public Folder Store in the selection list I received the same error.
It was, indeed, due to the fact that my system account that BackupExec uses was hidden from the address book as was stated in the earlier post. To fix:
1. Open Active Directory Users and Computers and find the account under which your BackupExec services run. This will likely be either "Administrator" or some other Domain Admin account (in my case I created a seperate Domain Admin account for BackupExec services)
2. Right-Click | Properties | Exchange Advanced tab
3. Make sure the check box called "Hide from Exchange address lists" is not checked. This will publish the account in the GAL.
Granted, your users will be able to see it now in Outlook when they use the GAL to pick recipients, but I'm not sure that there's a way around that. This is just a guess, but I think that after you make your initial selection in BackupExec you can hide the address from the GAL again and it will work. I try to leave my admin account hidden from the GAL if I can.
-Chris