Arg! PG not using index on an analyzed table

All-

I'm loathe to ask this, the #1 newbie question, on any of the postgresql
lists: whadda I do if a query's not using an index? I've analyzed 'til
I'm blue in the face.

I had a database in 7.4.6 on a RH7.3 box. I dumped and restored to a new
7.4.6 cluster on a new SuSE 9.2 box. I analyzed.

A query (shown below) takes 67 seconds on the new box and 76
milliseconds on the old one. The explain says why: an index.

Does anyone know what's going on here? I vaguely remember that
postgresql keeps frequency estimates of words... is the problem that the
new db doesn't have such estimates and therefore incorrectly guesses
that an index is better?

Thanks,
Reece

new=> explain select pseq_id from palias where alias~'^TR13B_HUM';
QUERY PLAN
---------------------------------------------------------------------------------------------------------------- Nested Loop (cost=0.00..550666.11 rows=1 width=4)
-> Seq Scan on paliasorigin pa (cost=0.00..550663.05 rows=1
width=4)
Filter: (alias ~ '^TR13B_HUM'::text)
-> Index Scan using pseqalias_one_iscurrent_per_palias_id on
pseqalias pv (cost=0.00..3.05 rows=1 width=8)
Index Cond: (pv.palias_id = "outer".palias_id)
Filter: (iscurrent = true)
(6 rows)

old=> explain select pseq_id from palias where alias~'^TR13B_HUM';
QUERY PLAN
--------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.00..7.57 rows=1 width=4)
-> Index Scan using paliasorigin_alias on paliasorigin pa
(cost=0.00..4.49 rows=1 width=4)
Index Cond: ((alias >= 'TR13B_HUM'::text) AND (alias <
'TR13B_HUN'::text))
Filter: (alias ~ '^TR13B_HUM'::text)
-> Index Scan using pseqalias_current_palias_id_aliases on pseqalias
pv (cost=0.00..3.06 rows=1 width=8)
Index Cond: (pv.palias_id = "outer".palias_id)
Filter: (iscurrent = true)
(7 rows)

--
Reece Hart, http://harts.net/reece/, GPG:0x25EC91A0