Mmm...got 1 of 2 choices then:
1. Reinstall SP4, and then patch BE 12.5 with all the available patches after SP4. Maybe 1 of them fixes your issue.
2. Uninstall SP4 and run SP3 for a while. Don't forget to patch with all available patches after SP3 was released (in other words, relevant to SP3). Once stable and your backups are running, look into patching with SP4.
If you can create a test VM somewhere, and load your BE database onto a trial version of Backup Exec, you can see whether or not SP4 does affect that. Only way to know if it is your installation or now...