Index not used for simple query, and yes I ran vacuum analyze

I RTFM but I'm still confused.  I have a table, headers

> mab=> \d headers
>                                 Table "headers"
>  Attribute |  Type   |                        Modifier
> -----------+---------+---------------------------------------------------------
>  header_id | integer | not null default nextval('headers_header_id_seq'::text)
>  part_id   | integer | not null
>  key       | text    |
>  value     | text    |
> Index: headers_pkey

with 13 million rows:

> mab=> select count(*) from headers;
>   count
> ----------
>  13411618
> (1 row)

I have indexed the table by part_id:

> mab=> \d headers_ref_idx
> Index "headers_ref_idx"
>  Attribute |  Type
> -----------+---------
>  part_id   | integer
> btree

And I have just run `vacuum analyze'. But the index isn't used:

> mab=> EXPLAIN SELECT * FROM headers WHERE part_id = 10;
> NOTICE:  QUERY PLAN:
>
> Seq Scan on headers  (cost=100000000.00..100361471.22 rows=22 width=32)
>
> EXPLAIN

The full table scan is extremely expensive (over 5 minutes wall clock
time).  `set enable_seqscan = off' doesn't cause the index to be used
either:

> mab=> set enable_seqscan = off;
> SET VARIABLE
> mab=> explain  SELECT * FROM headers WHERE part_id = 10;
> NOTICE:  QUERY PLAN:
>
> Seq Scan on headers  (cost=100000000.00..100361471.22 rows=22 width=32)
>
> EXPLAIN

According to the archives, the query planner decides whether to use an
index on a column based on the frequency of the most common value for
that column.  But that's only ~200 rows, out of 13 million:

> mab=> SELECT part_id, count(*) AS count FROM headers GROUP BY part_id ORDER BY count DESC LIMIT 10;
>  part_id | count
> ---------+-------
>   561415 |   219
>   114157 |   219
>   561414 |   219
>   114158 |   215
>   561418 |   215
>   561421 |   215
>   558872 |    74
>   558869 |    67
>   141780 |    62
>   202113 |    60
> (10 rows)

You'd think the index would still be cheaper.  It's almost like it
doesn't exist.  I tried removing and recreating it (and running vacuum
analyze again), but that didn't help.

(This is Postgres 7.1.2 under FreeBSD 4.4.)