I have a disk that is used only for timemachine connected by USB.
Everything seemed fine and I shut my computer down as normal one evening, but on powering up again I got this error:

I tried to run first aid in Disk Utility as a first fix, and got the following errors:

I tried to follow step 7.9 of the FAQ, but testdisk showed that both file headers were OK.

Are there any other suggestions? I can read the disk fine, but I can't add new backups to it. I know that trying to copy a timemachine backup to another disk will make it take up exponentially more diskspace than the current size-on-disk, because it will make a new copy of each file rather than just a link. I don't have any software to perform a byte-by-byte clone.
At the moment I'm thinking of just reformatting the disk and restarting my TimeMachine backup - I don't think I'll lose anything if I do it now.