ML and still get ".....TM must create a new backup.." error

I too have the problem, and have no idea why. It did not happen when I ran Snow Leopard, but it did happen with Lion, and it continues to happen with Mountain Lion. Every few weeks, I get the error message. The last time, I actually needed to use the backup, but could not (I didn't try the filesystem repair procedure mentioned above). I have a Mac Pro, and I have switched to using an internal drive for Time Machine (not the drive I use for my system or data; in fact, most of my data lives on my Readynas). An internal drive is not as safe as a Time Machine backup stored on a readynas located in another room of my house, but the frequent failures of the backups stored on the readynas have pretty much made them useless.

Hopefully, this will be fixed. I don't know if the problem is with the Readynas or with MacOS, but it sure is a problem.