Please check HKLM\Software\Symantec\Backup Exec For Windows\BEDatabase\
 
Does it have the proper server name?
Is the Databse attached in SQL?

You can run the BEutility.exe to change the server name.
Running this should clear up any thing that is not correct in the registry for the old server name.
You will run the "Update Configuration for New Media Server Name" in the Beutility.exe.

Make sure there is no problem in the registry where almost half of the registered dlls for Backup Exec and/or MDAC were pointing to a non-existent (deleted) network drive.
For one of old user of symantec BE  : Somehow the drive letter in the path designation for the location of the DLLs had been changed to the home drive "H:\".  I did a search and replace to change the H:\ to a C:\ and restarted.  This worked for him

1)
Referring to your reply #8 : what do you see in the registry for the Instance names ?
Catalog Database Instance Name
Server Database Instance Name
The thing is: when I use the BEUtility to check my database, everything seems normal.
But when trying to start this Backup Exec Device & Media service, error 536928979 shows up.
Also, my media server (the only one there is) status shows as "Unknown" in BEUtility...

2)
Another question : are you using a service account for all  Backup Exec services ?
If yes, does this service account  belong  to a particular Local Group  on your Server 2003 ?
I gave the service account (actually it is the SQL service account) all the required user rights via the Domain Security Policy snapin :

    * Log on as a service
    * Act as part of the operating system
    * Create a token object
    * Manage auditing and security log
    * Backup files and directories
    * Restore files and directories

I know this is old, but I had the same issue. After trying to use beutil to move my database from sqlepress to SQL 2008 on a different server none of the services would start. I ended up uninstalling BE and reinstalling (leaving the old files in place and pointing the install at the SQL 2008 server for the database). The device and media service failed to start and I had the same error as the original poster. I found if I changed the logon for the service account to domain\administrator it would start, after checking my service account was a dbowner and public for the BE databases I changed the default database for that user to Master (might not have done anything) and gave the user the sysadmin server role (which I think fixed it).
If you're looking for the correct registry settings for the database path when you're moving your db to a remote server:
HKLM\Software\Symantec\Backup Exec For Windows\BEDatabase\
Catalog Database Server Name: <SQL server hostname>
Server Database Log Path: <Drive letter>:\Logs (this is the path where the LDF files reside on the SQL server)
Server Database Path: <Drive letter>:\Data (this is the path where the MDF files reside on the SQL server)
Server Database Server Name: <SQL server hostname>
The other keys are blank, my SQL server has just one default instance for the databases so nothing was required for the Instance name keys.
After all that I didn't even restore my SQL database, it was only 15MB and I don't seem to be missing anything. The catalogs, data, idr, logs, reports and the besernum.xml files seem more important.

My customer called me to have a look for a problem that they have.

They have a small domain and while upgrading hardware they created new domain. Their Backup exec is running now on the new DC server.

This server used to be an file server and no they promoted it to DC. They tried to reinstall Backup exec and it works now, but can I import the old databases to new installation? I need to do a restore job, but I don't have backups!