since upgrading to El Capitan, every time my machine tries to make a backup to my Time Capsule, it prompts me with the aforementioned message.
after researching and finding not much, I decided to blow away my long history of backups and create a new one as suggested. the backup succeeded but the second time it tried to do a backup it failed again.
so now I have to create a brand new backup (of the whole disk) every time I want to make a backup?
this worked fine on Yosemite!