Hello,
Were there any other changes made on the server? Do the other services start well? Try creating a new account with administrator privileges and use this account for all the services except the remote agent service which should run under the local system account.
If the issue persists, run a database repair as per the technote below:
Title: How to run a Backup Exec database repair when the original Backup Exec database is found to be inconsistent
http://support.veritas.com/docs/265180
Revert if the problem persists.
Note : If we do not receive your reply within two business days, this post would be marked ‘assumed answered’ and would be moved to ‘answered questions’ pool.
Regards.