Data comparison SQL in PG 8.2.9

Hi. I have a large table that has a modify_date field in it, which is
timestamp without time zone.

I used to be able to do queries like these in 8.2.3 --

select id from users where modify_date = '2009-01-08' limit 1;
select id from users where modify_date > '2009-01-08' limit 1;

Suddenly these are returning:

id
----
(0 rows)

Time: 11.635 ms

I can see through other SQL that there are rows with these dates in
them! My "\d users" shows these two relevant entries about
modify_date:

Table "public.users"
Column | Type |
Modifiers
-----------------------+-----------------------------+------------------------------
modify_date | timestamp without time zone |
....
Indexes:
"new_idx_modify_date" btree (modify_date) WITH (fillfactor=75)

Any ideas why? I ran an explain analyze and this is the output:

******
=# explain analyze select id from users where modify_date =
'2009-01-08' limit 1;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..0.37 rows=1 width=8) (actual time=0.082..0.082
rows=0 loops=1)
-> Index Scan using new_idx_modify_date on users (cost=0.00..4.12
rows=11 width=8) (actual time=0.074..0.074 rows=0 loops=1)
Index Cond: (modify_date = '2009-01-08 00:00:00'::timestamp
without time zone)
Total runtime: 19.484 ms
(4 rows)

Time: 19.940 ms
******

Another weird thing is that a query that has ">" a certain
modify_date, even just yesterday as the date condition, takes a LONG
time and is almost unusable.

Appreciate any pointers.

Thx!