Apple - Time Machine Backup Failed

I had an issue with backups not completing and I solved it by deleting the partially created backup folder.

First turn time machine off (System Preferences > Time Machine > Off)

Navigate to /Volumes/VOLUMENAME/Backups.backupdb/COMPUTERNAME/, where you will see a list of folders dated by when the backup was created. If you see a folder with .inProgress in the name, move it to the trash.

Turn time machine back on and complete a backup. If it fails again, I'd recommend taking a look at the resources here: http://pondini.org/TM/C10.html