fsck_hfs cannot repair a Time Machine volume

Greetings.

I am using Time Machine to backup my iMac drive to an external LaCie d2 Quadra connected via FireWire. The setup worked fine for years, first on Snow Leopard, then on Lion, the on Mountain Lion (currently running ML 10.8.2). A few days ago I got an error: Time Machine could not back up to the FireWire volume.

I ran Disk Utility on the external drive. It ran for over 1 hour, then terminated with the error:

Disk Utility can’t repair this disk. Back up as many of your files as possible, reformat the disk, and restore your backed-up files.

I wanted to try to fix the drive before reformatting it. I searched these forums and Google; most suggestions were variations on the theme 'run fsck_hfs'. Eventually I used this command, and this was the result:

prompt$ sudo fsck_hfs -f -r -d /dev/disk1s2

journal_replay(/dev/disk1s2) returned 0

** /dev/rdisk1s2

Using cacheBlockSize=32K cacheTotalBlock=16384 cacheSize=524288K.

Executing fsck_hfs (version diskdev_cmds-557~393).

** Checking Journaled HFS Plus volume.

The volume name is LaCie TM

** Checking extents overflow file.

** Checking catalog file.

** Rebuilding catalog B-tree.

CreateNewBTree returned 5

** The volume LaCie TM could not be repaired.

volume type is pure HFS+

primary MDB is at block 0 0x00

alternate MDB is at block 0 0x00

primary VHB is at block 2 0x02

alternate VHB is at block 1468006398 0x577ffffe

sector size = 512 0x200

VolumeObject flags = 0x07

total sectors for volume = 1468006400 0x57800000

total sectors for embedded volume = 0 0x00

CheckHFS returned 5, fsmodified = 0

prompt$

I searched the Web for error codes 'CreateNewBTree returned 5", or "CheckHFS returned 5", to no avail.

Is reformatting the disk really my only option? Does anybody have any other suggestion?

Thanks for your help!