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.