I recently migrated a customer from BE 9.1 on 32 bit Windows 2000 to BE 12.5 on 64 bit Windows 2003 with a change of server name as well so it can be done and your scenario is (in theory) simpler as you already run 12.5 on the original server.
I have however not checked going from Windows 2003 to 2008 but as Backup Exec would still be running in SQL Express would expect it to work.
basic steps (which closely match the document are)
1) Install 64 bit Backup Exe on the new server with the same SP level as on old server.
2) Shutdown services on both servers and copy the database files, Backup to disk folders and catalog files from one server to the other
3) Startup ONLY the SQL service on the new server
4) Run the command to change the name of the server in the database
5) Start up the Backup Exec Services
6) In the BEWS console configure your hardware (tape devices, backup to disk folders) for the new server.
7) Change all the jobs so that they target the new backup devices.
8) Delete the references to the old backup devices
9) Correct any backup selection lists that might need modifying
10) Correct the advertising/publishing of any remote servers so that they address the new server.
Note these notes only apply to a basic server and do not cover things like DLO, CPS or CASO.
Also as a recommendation I would put all the jobs on hold on the original server before shuttting down the services and copyying the database as then no jobs will try and run on the new server until you have corrected the configs and additiionally you will be able to restart the services on the old server to compare settings without having any jobs start on the wrong server.
