I've managed to get Time Machine to resume doing backups using this backup volume without re-initialising the disk and losing the existing backups.

If you check in the Backups.backupdb directory under the name of the machine you're trying to use Time Machine on, you will see a directory with directories consisting of a date and time, as well as a directory called "Latest". If backupd is interrupted it looks like it leaves behind a folder with the date and time of the last backup and .inProgress on the end. So in my case, it was called "2008-11-24-100439.inProgress". If you delete this directory and resume Time Machine, it appears to not have the same error.

I still need to check whether there are any problems with the other backups on the volume, but at least Time Machine is working at the moment.