Reading about this issue further in the FAQ, it seems that I should ensure that Postgres has adequate and accurate information about the tables in question by regularly running VACUUM ANALYZE, something I don't do currently.
Well then you'll get rubbish performance always in PostgreSQL...I strongly suggest you run autovacuum if you don't really understand PostgreSQL vacuuming/analyzing.
Chris
