Issues with scheduled backups

I have been having issues getting my nightly scheduled backups to complete. I am recieving the following error on the clients that are failing:

1 retry attempted

No Full Backups of this save Set were found in the media database; performing a full backup

39078:save: RPC Error: RPC Send operation failed; errno= An established connection was aborted by the software in your host machine

I am recieving this error on a Windows 2003 R2 server on multiple save sets. Any ideas as to what is happening?

Thanks