Superblock invalid (but only sometimes)

Over at bug #97206 we have the error below, but only sometimes...

fsck.ext3: No such file or directory while trying to open /dev/sdb1

/dev/sdb1:
The superblock could not be read or does not describe a correct ext2
filesystem. If the device is valid and it really contains an ext2
filesystem (and not swap or ufs or something else), then the superblock
is corrupt, and you might try running e2fsck with an alternate superblock:
    e2fsck -b 8193 <device>

How do we rebuild/recover the superblock? Sometimes it boots fine without any complaints which is rather strange. I have tried to repair it with fsck and get

duncan@duncan-desktop:~$ sudo fsck -r -t ext3 /dev/sdb
fsck 1.40.8 (13-Mar-2008)
e2fsck 1.40.8 (13-Mar-2008)
fsck.ext3: Superblock invalid, trying backup blocks...
fsck.ext3: Bad magic number in super-block while trying to open /dev/sdb

The superblock could not be read or does not describe a correct ext2
filesystem. If the device is valid and it really contains an ext2
filesystem (and not swap or ufs or something else), then the superblock
is corrupt, and you might try running e2fsck with an alternate superblock:
    e2fsck -b 8193 <device>