What I've noticed is that when you get this error the Volume Shadow Copy service on the server being backed up is not started. If you start the service, then rerun the backup, it will run normally, without the error.
It's been several years since I've used Backup Exec, but I seem to recall that this was an issue back with BE versions 10 & 11, as well. I also seem to remember that there was a work-around or "technique" to eliminate that behavior, which worked. But I cannot remember what it was...still searching.