Selecting max(pk) is slow on empty set

This is on a fresh pg_restore copy that I have additionally vacuumed
and analyzed. These queries, on a table containing 2.8 million rows,
are very fast:

# select count(*) from user_messages where user_id = 13604;
 count
-------
     0
(1 row)
Time: 0.604 ms

# select * from user_messages where user_id = 13604;
 id | user_id | sender_id | sent_at | dismissed_at | message
----+---------+-----------+---------+--------------+---------
(0 rows)
Time: 0.678 ms

But doing a max() on this empty set takes a long time to run:

# explain analyze select max(id) from user_messages where user_id = 13604;

         QUERY PLAN

------------------------------------------------------------------------------------------------------------------------------------------------------
Result  (cost=633.19..633.20 rows=1 width=0) (actual
time=339160.704..339160.704 rows=1 loops=1)
   InitPlan
     ->  Limit  (cost=0.00..633.19 rows=1 width=4) (actual
time=339160.700..339160.700 rows=0 loops=1)
           ->  Index Scan Backward using user_messages_pkey on
user_messages  (cost=0.00..633188.12 rows=1000 width=4) (actual
time=339160.697..339160                 Filter: ((id IS NOT NULL) AND
(user_id = 13604))
 Total runtime: 339160.770 ms
(6 rows)

Note that it's using the correct index -- user_messages_pkey is on the
id attribute. (Why rows=1000 here?)

PostgreSQL 8.2.5 on Linux and OS X Leopard.

Alexander.