"Identity of backup disk has changed" error.

A couple days back I got the annoying "Identity of backup disk has changed" error. I dismissed it thinking nothing of it but got it again last night and I'm now starting to get concerned and want to nip this in the bud (after all, backups are important!)

I'm running a 2TB time capsule (the model prior to the new "tall" model). I had a 2TB external HDD plugged into to that time capsule which my third mac had been backing up to (I have two other macs backing up to the time capsule itself and there's not enough room for the third machine). Recently I purchased a 4TB external drive to increase my storage and replace the 2TB drive that the machine was currently backing up to.

I opted to clone the 2TB drive to my new 4TB drive to ensure all the files copied over properly (I was originally doing it manually but had the finder copies fail out a couple times), and then deleted the original backup sparse bundle to start fresh.*

Now since doing so I've had this issue a couple of times. I've read the Apple Help Article*and none of the four options are the case.

I have also been using this new 4TB drive as network attached storage and have been copying some files over there a few times and did notice it felt a little slow. I'm starting to worry that maybe the disk itself is a dud and needs to be replaced (despite being brand new).*

Any suggestions? Maybe it's just a fluke these two times? But I never had this issue prior to changing the disk, and never ONCE had the issue with the other two machines backing up to the Time Capsule itself.