BUG #5689: UPDATE locks index before table resulting in deadlock

The following bug has been logged online:

Bug reference: 5689
Logged by: Peter Ajamian
Email address: peter(at)pajamian(dot)dhs(dot)org
PostgreSQL version: 8.4.4
Operating system: CentOS 5.5
Description: UPDATE locks index before table resulting in deadlock
Details:

I got this error just now:
ERROR: deadlock detected
DETAIL: Process 24135 waits for AccessExclusiveLock on relation 17585 of
database 16922; blocked by process 13060.
Process 13060 waits for RowExclusiveLock on relation 17029 of
database 16922; blocked by process 24135.
Process 24135: REINDEX DATABASE "emailmarketer"
Process 13060: UPDATE jobs SET lastupdatetime='1286028903' WHERE
jobid='1165'
HINT: See server log for query details.
STATEMENT: REINDEX DATABASE "emailmarketer"

relevant info:
emailmarketer=# select 17585::regclass, 17029::regclass;
regclass | regclass
-----------+----------
jobs_pkey | jobs
(1 row)

emailmarketer=# explain UPDATE jobs SET lastupdatetime='1286028903' WHERE
jobid='1165';
QUERY PLAN
------------------------------------------------------------------------
Index Scan using jobs_pkey on jobs (cost=0.00..8.27 rows=1 width=972)
Index Cond: (jobid = 1165)
(2 rows)

From what I can understand, the UPDATE is trying to lock the index before
locking the table. This results in a deadlock with the REINDEX which locks
the table before the index. UPDATE should be locking the table first which
would avoid the deadlock.