I had the same problem with 6.5.3. It turns out that there is a "known"
(at least to the developers; I haven't seen it documented anywhere) problem
in 6.5:
if your postgresql was compiled with Locale support on, index searches of
the form
LIKE 'foo%' go very, very slow (much slower than deleting the index and
forcing a sequential search).
The solution is to recompile postgresql with Locale off. Note that I tried
to use the RPM that claims to be compiled this way, but it didn't help;
I had to recompile myself from the source RPM. Once I did the search
on 340,000 rows went from 20 seconds to 0.1 seconds.
7.0 supposedly fixes this, but I haven't tried it.