I've gone through all the points in the checklist, and the problem still appears. I ran a diagnostics check from within Backup Exec, and what I see is that the administator user is not said to be a Domain Admin:
Local Group Memberships for Backup Exec service account MYDOMAIN\administrator on \\MYSERVER
Offer Remote Assistance Helpers
Denied RODC Password Replication Group
Administrators
Users
MYDOMAIN\administrator is a member of the following groups:
MYDOMAIN\Domain Users
Everyone
BUILTIN\Administrators
BUILTIN\Users
BUILTIN\Pre-Windows 2000 Compatible Access
BUILTIN\Certificate Service DCOM Access
NT AUTHORITY\SERVICE
NT AUTHORITY\Authenticated Users
NT AUTHORITY\This Organization
LOCAL
MYDOMAIN\administrator has the following privileges:
Create a token object
Adjust memory quotas for a process
Add workstations to domain
Act as part of the operating system
Manage auditing and security log
Take ownership of files or other objects
Load and unload device drivers
Profile system performance
Change the system time
Profile single process
Increase scheduling priority
Create a pagefile
Back up files and directories
Restore files and directories
Shut down the system
Debug programs
Modify firmware environment values
Bypass traverse checking
Force shutdown from a remote system
Remove computer from docking station
Enable computer and user accounts to be trusted for delegation
Perform volume maintenance tasks
Impersonate a client after authentication
Create global objects
Increase a process working set
Change the time zone
Create symbolic links
Could this be anything? I'm shooting in the dark, here...:mansad: