Hi Joshua,
If I were you, I would make a copy of the Catalog, DATA folders. Then power down the Media Server and install Backup Exec to the new server keeping the same host name as the old Media Server. Once its installed, put the new licences. Stop all BE services, replace the CATALOG, DATA folders and then start services again. At this point BE will be as it was in the previous installation. Now you can change the server name and then apply the following technote in order to update the new server name in the BEDB: http://seer.entsupport.symantec.com/docs/277063.htm
If the DLO service still does not came up after this change, please refer to this article: http://seer.entsupport.symantec.com/docs/286456.htm
Keep in mind that all your DLO users will keep pointing to the old server name, therefore you will need to update each client.
The best thing would be to mantain the same server name, but if you cant, the above procedure will do it.
Regards,