index usage ... strange !?

He's a small example and I'm trying to speed up this query and I can manage it :-(

The table:
P3AT:
AO - char(15), with indexAT - Integer, with index AV - VARCHAR(80), with index valindCI - Integer, with index

We've about 23000 rows in this table. I would like to execute:
SELECT AO,AT,AV FROM P3ATWHERE EXISTS( SELECT AO FROM P3AT WHERE AV='12' AND AT=12 AND CI=17)

Explain gives me:
Result(946.19,0,0)  InitPlan    -> INdex Scan using valind on p3at (222,265,12)    (fine !)  ->Seq Scan on p3at
(946,22235,26)                   (urgghhh ?)
 
This statement takes about 2s to return the results.
The select statement within exists just needs 23ms to find the AO value !
SELECT AO FROM P3AT WHERE AO='12'
EXPLAIN GIVES ME:
 INDEX SCAN USING ATROWIND ON P3AT (2,2,12)
In general I expect for each unique AO about 10-12 result rows. I've done 
several vacuum analyze (the first one crashed my database by the way :-(, this
tool is really making me crazy - claiming that it can't remove the lock :-().
The reason seems to be the seq scan ... therefore how can I get rid of it !
I use PSQL 6.5.3 under SuSE 6.1.
Marten