Issues with Time Machine - new backup must be created

Well, just a follow up really…

You’re absolutely right about it only be a temporary solution.

After purchasing Final Cut Pro I was forced into updating to Mavericks.  (I doubt this was the issue though)

I am still able to enter time machine, but I cannot perform backups.  I get the same error message as before about verification and starting a new backup.

Really disappointed.  It’s a great device, but this just makes it unusable.