Deadlock with REINDEX TABLE

Hi, I'm hoping some one can help me figure out how I ended up with a deadlock while running my reindex script last night.  It basically partitions our table set and goes through each group of tables in parallel running REINDEX TABLE on each table in that group with each group having its own log.  Anyways, I woke up this moring to find this in one of the logs: 

Mar 21 19:36:18  [info] User Info: REINDEX TABLE emma_messages_email_queue; [nativecode=ERROR:  deadlock detected

DETAIL:  Process 12912 waits for AccessExclusiveLock on relation 138763808 of database 16384; blocked by process 15217.

Process 15217 waits for RowExclusiveLock on relation 17111 of database 16384; blocked by process 12912.]

Relation 138763808 is the primary key index on the table relation 17111.

Proc 12912 is the REINDEX and proc 15217 is the contending query, I'm assuming it was an update due being a RowExclusive lock.

How did this happen?  Does REINDEX TABLE not take out the locks for each of the table's indexes at the same time (there was another index on the table but I'm not sure whether or not it was reindexed or not)?  Do REINDEX TABLE and UPDATE not take out their locks in the same order (i.e. lock table, lock indexes)?