I figured out what the problem was. When I started using the drive as a Time Machine backup, I just plugged it in without taking a look at the partioning other than size. What I had was a couple of partitions that were both formatted as MSDOS and not with GUID. Although Time Machine will happily write to a MSDOS partitition, it doesn't seem to want to use it when you try and launch time machine.
I had done a couple of successful repairs with no errors so I ruled that out.
I repartitioned the drive, let Time Machine do a backup to the new GUID journaled FS and it worked straight away. I'm sure there is an Apple manual that says make sure you're drive is GUID journaled but I didn't put 2 and 2 together.
All seems happy now.