I ran into this error recently at one of my clients with their new Backup Exec 2012 implementation. The jobs would sometimes work, but mostly they would fail with the error above. They would also fail at seemingly random byte counts. The implementation was backing up two servers. One of the servers was also the media server and this local backup always succeeded as expected and without incident. The other server, the one that was often failing, was the one with the remote agent.
This made me quickly look towards the network. As a test I kicked off the problematic backup and monitored the network bandwidth usage in Task Manager on both servers. I also had a continuous ping going between the two servers. The first thing that became apparent was that the network bandwidth (100Mb switch) was completely saturated during the backup. Both servers continually reported a steady hold at 100% network utilization.