Oh, and you can use the sledge hammer of tuning by using the
set enable_xxx = off
settings for the planner. It's not a normal way to tune most queries,
but it certainly can let you know if the problem is using the index or
not.
psql mydb
\timing
select count(*) from table where field > 12345;
set enable_seqscan=off;
select count(*) from table where field > 12345;
and compare them. run each a few times, since the cache will affect
the performance.