Very slow queries on 8.1

I'm porting an application from Sybase and I've noticed that similar
application functions take 2 to 3 times longer on postgres than they
used to on the same machine running under Sybase. I've tried changing
various "performance tuning" parameters, such as shared_buffers,
effective_cache_size, etc but there's little or no effect. I'm
beginning to think there's a deeper root cause to the slowness.

Right now, I'm working on a test case that involves a table with ~360k
rows called "nb.sigs". My sample query is:

select * from nb.sigs where signum > 250000

With no index, explain says this query costs 11341. After CREATE INDEX
on the signum field, along with an ANALYZE for nb.sigs, the query costs
3456 and takes around 4 seconds to return the first row. This seems
extremely slow to me, but I can't figure out what I might be doing
wrong. Any ideas?

(If necessary, I can write an entire script that creates and populates a
table and then give my performance on that sample for someone else to
check against.)