Slow indexscan

Hello group

I have a problem with a simple index scan using the primary key of a table
taking too long.

Relevant facts:
pg version 7.3.4 (yeah very old, we are upgrading asap)

postgresql.conf:
shared_buffers = 25000
random_page_cost = 2
effective_cache_size = 200000
sort_mem = 20000

Table:
db=# \d tbl_20070601
Table "public.tbl_20070601"
Column | Type | Modifiers
------------------+-----------------------+-----------
validtime | bigint | not null
latitude | double precision | not null
longitude | double precision | not null
.....
parname | character varying(20) | not null
....
(table has a lot of columns but these are the most important ones)

Indexes: tbl_20060601_pkey primary key btree (validtime, latitude,
longitude, ..., parname, ...)

Validtime is a timestamp for the row (not my design).

the query:
db=# explain analyze select * from tbl_20070601 where validtime between
20070602000000 and 20070602235500 and latitude=60.2744 and
longitude=26.4417and parname in ('parameter');

QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Index Scan using tbl_20070601_pkey on tbl_20070601 t1
(cost=0.00..365.13rows=13 width=137) (actual time=
120.83..10752.64 rows=539 loops=1)
Index Cond: ((validtime >= 20070602000000::bigint) AND (validtime <=
20070602235500::bigint) AND (latitude = 60.2744::double precision) AND
(longitude = 26.4417::double precision))
Filter: (parname = 'temperature'::character varying)
Total runtime: 10753.85 msec
(4 rows)

db=# select count(*) from tbl_20070601;
count
---------
3715565
(1 row)

the query is only returning 539 rows but it takes more than 10 seconds to
execute. The table has only inserts and never deletes or updates and it has
been analyzed recently.

Is there anything to tweak with the query and/or postgresql, or should the
hardware be inspected? Server is 2-CPU 4GB RAM blade-server with a fibre
connection to a disk subsystem. Any more information I can give about the
system?

Regards

MP