Index not used, performance problem

Hi!

I've got the following problem:
PostgreSQL 7.2.1-2 (Debian) on Duron/700MHz, 512MB, IDE hdd (laptop).

I've got a table that has 6400 rows, an index on the deleted, nachname,
vorname and hvvsnummer attributes, and my O-R wrapper generate queries
like this:

SELECT patient.id, patient.vorname, patient.nachname, patient.titel,
patient.geburtsdatum, patient.hvvsnummer, patient.geschlecht,
patient.adresse_id, patient.beruf, patient.kommentar, patient.cave,
patient.zusatzversicherung, patient.deleted FROM patient WHERE
((((patient.deleted = 'f') AND (patient.nachname LIKE 'K%')) AND
(patient.vorname LIKE '%')) AND (patient.hvvsnummer LIKE '%'))

This results in a SeqScan von patient. Even more curious is that simpler
queries like

select * from patient where deleted='f'; OR:
select * from patient where nachname LIKE 'K%';

all result in SeqScan on patient.

I've "analyzed" and "reindex" the table already multiple times, and
still PostgreSQL insists upon not using any index.

TIA for any pointers,

Andreas

mpp2=# \d patient
Table "patient"
Column | Type | Modifiers
--------------------+--------------+-------------
id | integer | not null
vorname | text | not null
nachname | text | not null
titel | text |
geburtsdatum | date |
hvvsnummer | text |
geschlecht | character(1) |
adresse_id | integer |
beruf | text |
kommentar | text |
cave | text |
zusatzversicherung | text |
deleted | boolean | default 'f'
Indexes: patient_deleted,
patient_hvvsnummer,
patient_nachname,
patient_vorname
Primary key: patient_pkey
Check constraints: "patient_geschlecht" (((geschlecht = 'm'::bpchar) OR
(geschlecht = 'w'::bpchar)) OR (geschlecht = '?'::bpchar))
Triggers: RI_ConstraintTrigger_352787,
RI_ConstraintTrigger_352789,
RI_ConstraintTrigger_352801,
RI_ConstraintTrigger_352803,
RI_ConstraintTrigger_352815

mpp2=# select count(*) from patient;
count
-------
6406
(1 row)

mpp2=# explain SELECT * FROM patient WHERE (patient.nachname LIKE 'K%');
NOTICE: QUERY PLAN:

Seq Scan on patient (cost=0.00..173.07 rows=272 width=70)

EXPLAIN
mpp2=# explain SELECT * FROM patient WHERE NOT deleted;
NOTICE: QUERY PLAN:

Seq Scan on patient (cost=0.00..157.06 rows=6406 width=70)

EXPLAIN
mpp2=# explain SELECT * FROM patient WHERE deleted='f';
NOTICE: QUERY PLAN:

Seq Scan on patient (cost=0.00..173.07 rows=6406 width=70)

EXPLAIN