Index not used on simple select

Hey,
I've been having this bizarre problem with some index on this one table.
The table has in the past had more than 9 indexes, but today I redid the
table and it still has the same problem.
I just did a dump of the schema, COPY'd the data out. Deleted all
postgres files, and installed 6.5.1.
The table has 3,969,935 rows in it.

Any ideas?

Here is the explain reports after both vacuum and vacuum analyze on the
table:
---------------------------------------------
parts=> explain select * from av_parts where partnumber = '123456';
NOTICE: QUERY PLAN:

Index Scan using av_parts_partnumber_index on av_parts (cost=3.55 rows=32
width=124)

EXPLAIN
parts=> explain select * from av_parts where nsn = '123456';
NOTICE: QUERY PLAN:

Seq Scan on av_parts (cost=194841.86 rows=3206927 width=124)

EXPLAIN
-------------------------------------------------

This is how I create the 2 indexes:
-------------------------------------------------
CREATE INDEX "av_parts_partnumber_index" on "av_parts" using btree
( "partnumber" "varchar_ops" );
CREATE INDEX "av_parts_nsn_index" on "av_parts" using btree
( "nsn" "varchar_ops" );
-------------------------------------------------

Table = av_parts
+----------------------------------+----------------------------------+-------+
| Field | Type |Length|
+----------------------------------+----------------------------------+-------+
| itemid | int4 not null default nextval ( |4 |
| vendorid | int4 |4 |
| partnumber | varchar() |25 |
| alternatepartnumber | varchar() |25 |
| nsn | varchar() |15 |
| description | varchar() |50 |
| condition | varchar() |10 |
| quantity | int4 |4 |
| rawpartnumber | varchar() |25 |
| rawalternatenumber | varchar() |25 |
| rawnsnnumber | varchar() |15 |
| date | int4 |4 |
| cagecode | varchar() |10 |
+----------------------------------+----------------------------------+-------+
Indices: av_parts_itemid_key
av_parts_nsn_index
av_parts_partnumber_index

Thanks,
Ole Gjerde