This table won't use INDEX until I DUMP/RESTORE it ?

I have a DB that appears to perform badly. A test of one table
with one of the typical queries gives me a query plan indicating
a Seq Scan;

DB=# EXPLAIN select pcref,pcseqnbr from catrecrel where pcbsref='something' and (pccaref is null or pccaref='') and pcpar is null order by pcseqnbr ;
NOTICE: QUERY PLAN:

Sort (cost=38266.65..38266.65 rows=4 width=58)
-> Seq Scan on catrecrel (cost=0.00..38266.61 rows=4 width=58)

Ok, that's no good, but it _should_ be using an index instead, and
if I dump this table, restore it onto a different (non-live) DB, and
try again, I see that it does indeed plan to use the index:

DB=# EXPLAIN select pcref,pcseqnbr from catrecrel where pcbsref='something' and (pccaref is null or pccaref='') and pcpar is null order by pcseqnbr ;
NOTICE: QUERY PLAN:

Sort (cost=469.92..469.92 rows=1 width=58)
-> Index Scan using ind_pcbsref on catrecrel (cost=0.00..469.91 rows=1 width=58)

Now, why is this? The first (live) DB is VACUUM ANALYSEd nightly, and
was done so again just before this test. Data, schema and indexes should
be the same in both (well it was dumped/restored directly from one to the
other).

The only fix I can think of is to dump and restore the whole DB, based on
the fact that a newly restored DB appears to work much better, but surely
I shouldn't have to do this? What else can i do to fix it?

Cheers,
CM

--
Chris Miles
http://chrismiles.info/