In order to troubleshoot the problem, we would suggest you please refer to the following technote :- Title:-VERITAS Backup Exec 9.0 Device & Media Service fails to start and "Event ID 1068" and "7001" error are reported in the Event Viewer.
http://seer.support.veritas.com/docs/256189.htm
And
Title:-After changing the VERITAS Backup Exec (tm) 9.x service account's password, the error "Database specified does not exist" may occur when starting the Backup Exec Device and Media Service.
http://seer.support.veritas.com/docs/265051.htm
If the issue persists, please refer to following steps:
1. Start Beutility and then select "Drop existing database and reload from base".
Refer to following technote:
http://seer.support.veritas.com/docs/254014.htm
Note: All media sets, backup-2-disk folder, and other settings will have to be created or configured again, if the option Drop existing database and reload from base is selected.
Server name may not appear in the right pane of the Beutility. You need to add the servername. Right-click on All Media Servers, and then select New Media Server. You may refer step (A. Configuring Backup Exec utility) mentioned in the following
technote:
http://seer.support.veritas.com/docs/254374.htm
2. You may change all Backup Exec services to manual and then reboot the machine. After reboot, start Backup Exec services. This step is for test purpose only. Verify the result and get back to us if problem still persists.