Backup Exec 12.5 should give you a 60-day trial license, so first things first, I would check that the license hasn't expired.
The easiest way is to simply open up Backup Exec, and check at the top...it will show you: x-days of 60 days used, or something to that effect.
I've upgraded all our servers from 11D to 12.5 using the trial license, whilst waiting for our 12.5 licenses, and haven't had any problems.
You can also check that all your services have started up correctly, and if you're backing up to tape, send a job to disk and see if you get the same issue.