Problems with a slow query using a simple JOIN

I've got a huge query which takes far too long to execute, and after
breaking it down I've located the following simple query that is causing
all the problems:

explain analyse SELECT * FROM tblmessages INNER JOIN tblcategories
ON (tblcategories.intcategoryindex = tblmessages.intcategoryindex);

NOTICE: QUERY PLAN:

Hash Join (cost=6.43..19999.14 rows=126935 width=392) (actual
time=1.09..1214.51 rows=126935 loops=1)
-> Seq Scan on tblmessages (cost=0.00..17771.35 rows=126935
width=364) (actual time=0.01..526.73 rows=126935 loops=1)
-> Hash (cost=5.74..5.74 rows=274 width=28) (actual time=1.03..1.03
rows=0 loops=1)
-> Seq Scan on tblcategories (cost=0.00..5.74 rows=274
width=28) (actual time=0.05..0.60 rows=274 loops=1)
Total runtime: 1344.15 msec

Both the fields in the join are indexed, both are int4s, one is a
primary key, and have run vacuum analyze etc. And whats more, if I do a
set enable_seqscan=false; to force it to use the indexes, it takes 5
times as long!

Can't for the life of me work out why such a simple join is taking so
much time.

Help!

Yours Unwhettedly,
Robert John Shepherd.

Editor
DVD REVIEWER
The UK's BIGGEST Online DVD Magazine
http://www.dvd.reviewer.co.uk

For a copy of my Public PGP key, email: pgp(at)robertsworld(dot)org(dot)uk