Hello,
As you want to perform the fresh install of Windows 2003 over existing windows 2000, then in this case you will hav eto do a fresh installation of Backup Exec.
Please note when you have installed BE v9.1 on windows 2000, the installation relates to the underlined operating system.Now if you want to use then same confoguration with windows 2003 on the same server it will not function properly cause the operating system differs.
As you have mentioned here that you have referred the Technote related to thsi issue, have you referred the following technote?
http://support.veritas.com/docs/260054
In your scenario we suggest you to upgrade the Backup Exec v9.1 to B Ev10.0 on Windows 2000 server and then upgrade the Whole OS to windows 2003 server.
If you have further queries please contact us.
NOTE : If we do not receive your reply within two business days, this post would be marked assumed answered and would be moved to answered questions pool.