Backend process termination + database corruption

Unfortunately, I can't tell you how the exact problem ocurred. All I
know is after checking my logs, I see the following:

ERROR:  DeleteTypeTuple: type "tmp_clm_empl" does not exist
Server process (pid 18240) exited with status 256 at Fri Dec 21 23:00:01
2001
Terminating any active server processes...
NOTICE:  Message from PostgreSQL backend:
 The Postmaster has informed me that some other backend died abnormally
and possibly corrupted shared memory.
 I have rolled back the current transaction and am going to terminate
your database system connection and exit.
 Please reconnect to the database system and repeat your query.
NOTICE:  Message from PostgreSQL backend:
 The Postmaster has informed me that some other backend died abnormally
and possibly corrupted shared memory.
 I have rolled back the current transaction and am going to terminate
your database system connection and exit.
 Please reconnect to the database system and repeat your query.
Server processes were terminated at Fri Dec 21 23:00:01 2001
Reinitializing shared memory and semaphores
DEBUG:  database system was interrupted at 2001-12-21 22:55:12 PST
DEBUG:  CheckPoint record at (1, 1434926108)
DEBUG:  Redo record at (1, 1434926108); Undo record at (0, 0); Shutdown
FALSE
DEBUG:  NextTransactionId: 6669205; NextOid: 11842876
DEBUG:  database system was not properly shut down; automatic recovery
in progress...
DEBUG:  redo starts at (1, 1434926172)
NOTICE:  PageAddItem: tried overwrite of used ItemId
FATAL 2:  heap_insert_redo: failed to add tuple
./postmaster: Startup proc 18280 exited with status 512 - abort

Subsequent attempts to restart Postgres gives me the message of:

DEBUG:  database system was interrupted being in recovery at 2001-12-21
23:21:33 PST
 This propably means that some data blocks are corrupted
 and you will have to use last backup for recovery.
DEBUG:  CheckPoint record at (1, 1434926108)
DEBUG:  Redo record at (1, 1434926108); Undo record at (0, 0); Shutdown
FALSE
DEBUG:  NextTransactionId: 6669205; NextOid: 11842876
DEBUG:  database system was not properly shut down; automatic recovery
in progress...
DEBUG:  redo starts at (1, 1434926172)
NOTICE:  PageAddItem: tried overwrite of used ItemId
FATAL 2:  heap_insert_redo: failed to add tuple
./postmaster: Startup proc 22045 exited with status 512 - abort

The platform this is running on is:
    PostgreSQL 7.1.3
    Solaris X86 8 7/01 release + ATA patch
    Dual Athlon XP 1600+
    Tyan S2460 MB
    768MB ECC DDR266 Memory