The easiest way to re-register the service is to run the 'fixinstall.bat' located in the install directory for Backup Exec System Recovery, note that this does require a reboot.
In a default installation, the fixinstall.bat can be found here;
C:\Program Files\Symantec\Backup Exec System Recovery
