Did you upgrade your version? or better:
before you did the whole "new installation thing", did you use a version of backup exec before 12.5?
And if so, have you ever gone to the licensing portal, and entered your upgrade notification ID?
If you did not, you propably miss some new 12.5 license keys.
In that case, call the symantec customer care center, they can re-send you the upgrade notification IDs, which enable you do the license upgrade in the licensing portal again. After that, you should be able to see all your current 12.5 license keys.