I did not, Ken. Surprisingly, I still run this version and was looking for a similar issue recently. That being said, the solution was actually not given, so I'm glad I could help, even if I'm 2 years, 5 months and 29 days too late.
Yes, in 9.x the exact Error Message is
Error 1065: "The database specified does not exist."
Event Type: Error
Event Source: Service Control Manager
Event Category: None
Event ID: 7023
Here's what happens. After changing the Backup Exec server...
1. Stop the Backup Exec Services.
2. Open a command prompt on the media server
3. Change the directory to the Backup Exec installation directory:
\Program Files\Symantec\Backup Exec
4. Type the follow and then press Enter:
catrebuildindex -r
5. ...