Tim,
It sounds like one of your table indicies became corrupted. I had a
similar thing happen to me before. To test this, try vacuuming each
table separately (i.e. 'vacuum verbose analyze tablename'). If each
table vacuums separately, then it is a problem with the main index (the
table of tables). In this case, you'll probably have to pg_dump and
restore the database (or possibly first try to drop the indicies and
re-create them).
-Tony