indexes no longer used after shutdown during reindexing

Hello all,
I have a database that was shut down, cleanly, during an 'reindex
table' command. When the database came back up, queries against that
table started doing sequential scans instead of using the indexes as
they had been up until that point.

We tried:
1) vacuuming the table (vacuum tblName)
2) reindexing the table (reindex table tblName)
3) dropping and recreating the indexes

but none of those actions helped. We ended up recreating the table by
renaming the table and doing a create table as select * from oldTable
and readding the indexes. This worked.

This problem presented itself as an application timing out. It took
several people, several hours to track this down and solve it.

Several months ago I had two other tables also stopped using their
indexes. Those times however I don't know if a database shutdown caused
the problem.

Has anyone had this problem? If so, what specifically is the cause? Is
shutting down a database during a table rebuild or vacuum an absolute no-no?

Any and all help or insight would be appreciated,
Matt