Have you recently applied any updated to Backup Exec. If yes, have updated all the Remote Agents (on VMs). Also I am not sure if you mean you are backing up to a tape of disk. If you are backing up to a tape device then make sure that you have the latest Symantec tape drives installed. If you are backing up to a B2D folder, is it local B2D as in on an Internal HDD or is it on a External device (USB HDD, NAS, SAN) If this is a Internal HDD, check for defragmentation (Caution - don't run defrag as it would destroy the whole B2D folder)
Other than this, have you made any changes to the Network in the past few days, it just might be some maintainance performed somewhere in the setup. That would be the best place to start looking for any cables/connections which are not secured properly.