Time Machine: The identity of the backup disk has changed

Question

I have a stock 2GB Time Capsule that I use to backup two macs using Time Machine.

Both machines have been backing up quite happily until the other day, one of the machines gave the following error

The identity of the backup disk has changed since the previous backup. The disk may have been replaced or erased, or someone may be trying to trick your computer into backing up to the wrong disk.

I have had issues with this one machine previously, it has been unable to access the Time Capsule a few times and I have had to delete and re-enable Time Machine backups for this machine.

NOTE: the other machine, during all this, has never had any issues with Time Machine backups.

So onto the information:

1. The machine with working TM backups is connected directly to the TC with ethernet
2. The machine with the problem TM backups is connected via Wifi to the TC on it's 5Ghz wifi connection.
3. The problem machine can connect and browse the TC via network
4. I changed the problem machine to use 2.4GHz wifi the last time this happened and it still happened
5. There are no external drives connected to the TC, backups are to the units internal drive
6. Both machines are OS X ML 10.8.2

So the question is, why is this happening on the one Mac?