Equality search on timestamp value returns no rows

PostgreSQL 8.1.4
RHEL 4.x

So we have run into an interesting problem I want to know if anyone else has encountered before. We have a scheduler process that 'hangs' on occasion and we have isolated the issue to Postgres not returning any records when there are actual records to return. Here is the table definition:

mxl=# \d mxl_scheduler_queue;
Table "public.mxl_scheduler_queue"
Column | Type | Modifiers
-----------------+--------------------------+----------------------------------------------------------
job_id | integer | not null default nextval(('mxl_id_seq'::text)::regclass)
type | integer | not null
id | integer | not null
scope | smallint | not null
status | smallint | not null default 0
start_time | timestamp with time zone |
created | timestamp with time zone | default ('now'::text)::timestamp(6) with time zone
status_modified | timestamp with time zone | default ('now'::text)::timestamp(6) with time zone
priority | smallint | not null
parent_id | integer |
parent_scope | smallint |

We run into a problem when an equality search on a timestamp column returns no records, even when there are records to return, as in this example:

mxl=# select * from mxl_scheduler_queue where status_modified = '2008-07-03 16:55:06.44695-06';
job_id | type | id | scope | status | start_time | created | status_modified | priority | parent_id | parent_scope
--------+------+----+-------+--------+------------+---------+-----------------+----------+-----------+--------------
(0 rows)

We have found that when we qualify the value with the timestamp clause, the records do return successfully:

mxl=# select * from mxl_scheduler_queue where status_modified = timestamp(5) with time zone '2008-07-03 16:55:06.44695-06';
job_id | type | id | scope | status | start_time | created | status_modified | priority | parent_id | parent_scope
--------+------+-------+-------+--------+------------------------+-------------------------------+------------------------------+----------+-----------+--------------
60589 | 2 | 59145 | 3 | 0 | 2008-07-02 15:00:00-06 | 2008-06-25 15:55:10.456385-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
60565 | 2 | 58976 | 3 | 0 | 2008-06-30 09:00:00-06 | 2008-06-23 09:55:11.604895-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
60087 | 3 | 59143 | 2 | 0 | 2008-07-01 10:00:00-06 | 2008-06-03 10:55:09.488425-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
60567 | 2 | 59143 | 2 | 0 | 2008-07-01 10:00:00-06 | 2008-06-24 10:55:15.021056-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
60094 | 3 | 58824 | 3 | 0 | 2008-07-01 13:00:00-06 | 2008-06-03 13:55:08.711156-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
60096 | 3 | 59145 | 3 | 0 | 2008-07-02 15:00:00-06 | 2008-06-04 15:55:11.212787-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
(6 rows)

And if we dump the data, drop the table, and reload the records, the equality search as shown here works just fine:

mxl=# select * from mxl_scheduler_queue where status_modified = '2008-07-03 16:55:06.44695-06';
job_id | type | id | scope | status | start_time | created | status_modified | priority | parent_id | parent_scope
--------+------+-------+-------+--------+------------------------+-------------------------------+------------------------------+----------+-----------+--------------
60589 | 2 | 59145 | 3 | 0 | 2008-07-02 15:00:00-06 | 2008-06-25 15:55:10.456385-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
60565 | 2 | 58976 | 3 | 0 | 2008-06-30 09:00:00-06 | 2008-06-23 09:55:11.604895-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
60087 | 3 | 59143 | 2 | 0 | 2008-07-01 10:00:00-06 | 2008-06-03 10:55:09.488425-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
60567 | 2 | 59143 | 2 | 0 | 2008-07-01 10:00:00-06 | 2008-06-24 10:55:15.021056-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
60094 | 3 | 58824 | 3 | 0 | 2008-07-01 13:00:00-06 | 2008-06-03 13:55:08.711156-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
60096 | 3 | 59145 | 3 | 0 | 2008-07-02 15:00:00-06 | 2008-06-04 15:55:11.212787-06 | 2008-07-03 16:55:06.44695-06 | 200 | |
(6 rows)

Any ideas why the equality search wouldn't work in the first case, but after reloading the table data it works just fine?

Thanks,

Keaton