Check the backupexec account permissions. I think it needs local admin on the server that its on.

I had the same problem on my test lab, i uninstalled/rebooted/reinstalled choosing the domain admin account and then everything worked fine.

This is taken from the backupexec help:

If this computer is in a domain, enter a Domain Administrators account, or an equivalent account that is part of the Domain Admins group. In the Domain list, select or enter the Domain name.

If this computer is in a workgroup, enter an Administrators account, or an equivalent account that is part of the Administrators group on the computer. In the Domain list, select or enter the computer name.

The account that you designate for Backup Exec services, whether it is a new account or an existing user account, is assigned the following rights:

Authenticate as any user and gain access to resources under any user identity.
Create a token object, which can then be used to access any local resources.
Log on as a service.
Administrative rights (provides complete and unrestricted rights to the computer).
Backup operator rights (provides rights to restore files and directories).
Manage auditing and security log.
Due to security implementations in Microsoft Small Business Server, the service account must be Administrator.