Hopefully this may help you. I performed three steps yesterday, and I don't know which one had the affect, but my backups worked fine last night.
1. From the Services console on my Exchange server, I opened the Backup Exec Remote Agent service, clicked the 'Recovery' tab, and changed all failure options to 'Take no action'. I don't want that service stopping, even restarting.
2. From the properites of my daily job in Backup Exec, on the Network page, I changed the Network Interface to the explicit device, rather than 'Use any available network adapter'.
3. From the properties of my daily job in Backup Exec, on the Advanced Open File page, I unchecked the 'Advanced Open File Option.
Bear in mind that for some time now, I've been rebooting my Exchange server before the backup takes place (every night), so you may need to reboot or at least restart some services to get this going.
Hopefully this carries on working for me, and helps you out too.