select max() much slower than select min()

ts_stats_transet_user_interval has ~48M rows. ts_id is the PK and there
is an index on ts_interval_start_time. I reindexed it and ran vacuum
analyze. Only SELECTs have been done since these operations.

cemdb=# explain select min(ts_id) from ts_stats_transet_user_interval a
where 0=0 and a.ts_interval_start_time >= '2009-6-16 01:00' and
a.ts_interval_start_time < '2009-6-16 02:00';

QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Result (cost=12.19..12.20 rows=1 width=0)
InitPlan
-> Limit (cost=0.00..12.19 rows=1 width=8)
-> Index Scan using ts_stats_transet_user_interval_pkey on
ts_stats_transet_user_interval a (cost=0.00..5496152.30 rows=450799
width=8)
Filter: ((ts_id IS NOT NULL) AND
(ts_interval_start_time >= '2009-06-16 01:00:00-07'::timestamp with time
zone) AND (ts_interval_start_time < '2009-06-16 02:00:00-07'::timestamp
with time zone))
(5 rows)
cemdb=# explain select max(ts_id) from ts_stats_transet_user_interval a
where 0=0 and a.ts_interval_start_time >= '2009-6-16 01:00' and
a.ts_interval_start_time < '2009-6-16 02:00';

QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Result (cost=12.19..12.20 rows=1 width=0)
InitPlan
-> Limit (cost=0.00..12.19 rows=1 width=8)
-> Index Scan Backward using
ts_stats_transet_user_interval_pkey on ts_stats_transet_user_interval a
(cost=0.00..5496152.30 rows=450799 width=8)
Filter: ((ts_id IS NOT NULL) AND
(ts_interval_start_time >= '2009-06-16 01:00:00-07'::timestamp with time
zone) AND (ts_interval_start_time < '2009-06-16 02:00:00-07'::timestamp
with time zone))
(5 rows)
[root(at)rdl64xeoserv01 log]# time PGPASSWORD=quality psql -U admin -d
cemdb -c "select min(ts_id) from ts_stats_transet_user_interval a where
a.ts_interval_start_time >= '2009-6-16 01:00' and
a.ts_interval_start_time < '2009-6-16 02:00'" min
--------------------
600000000032100000
(1 row)

real 1m32.025s
user 0m0.000s
sys 0m0.003s
[root(at)rdl64xeoserv01 log]# time PGPASSWORD=quality psql -U admin -d
cemdb -c "select max(ts_id) from ts_stats_transet_user_interval a where
a.ts_interval_start_time >= '2009-6-16 01:00' and
a.ts_interval_start_time < '2009-6-16 02:00'"
max
--------------------
600000000032399999
(1 row)

real 16m39.412s
user 0m0.002s
sys 0m0.002s

seems like max() shouldn't take any longer than min() and certainly not
10 times as long. Any ideas on how to determine the max more quickly?

Thanks,
Brian