I will add to this group... My wife's Mac is a Mid 2014 15" MBP she backs up wirelessly to our 2014 Time Capsule and she has been having this issue for the last month or two. The first time it happened I connected her mac by ethernet cable to our Time Capsule for the initial backup, but its now like that third or fourth time this same error has come up. My Mac is a Late 2011 15" MBP, I am hard wired to an external drive and running MacOS Sierra up to date with no issues.
If its always been Time Capsules, I am not sure if its the TimeMachine software or the Mac's system software, but this feels like a software bug. The only unsupported software my wife runs is Aperture, thats where her photo library lives (ugh!)
Time Machine completed a verification of your backups on “blahblah Time Capsule”. To improve reliability, Time Machine must create a new backup for you.