Was this an upgrade, or a clean install?
I remember that there was a similar problem with upgrades in an earlier version, but can't find the TechNote.
(Have I mentioned that I HATE the new "improved" search function?)
Have you tried removing all serials and shutting down/restarting all BackupExec Services, then re-entering your serials?