pg_autovacuum and REINDEX at the same time (?)

Hi.
I've been running autovacuum over a month now without any problems, but
today one of the critical tables got locked and made a pretty big mess. :)
We have a cron script that does REINDEX on this table every 5 minutes.
So i wonder if running REINDEX and VACUUM on the same table at the same
time may cause this deadlock?
Or can a VACUUM make so much trouble?

Version: PostgreSQL 8.1.4 on x86_64-pc-linux-gnu, compiled by GCC
x86_64-pc-linux-gnu-gcc (GCC) 4.1.1 (Gentoo 4.1.1)

Vacuum settings:
vacuum_cost_delay = 150
vacuum_cost_page_hit = 6
vacuum_cost_page_miss = 10
vacuum_cost_page_dirty = 20
vacuum_cost_limit = 150

 From the log:

2007-02-28 10:40:13 EET - LOG:  autovacuum: processing database "dbname"
2007-02-28 10:40:56 EET - postgres FATAL:  sorry, too many clients
already            (here i assume the table got completely locked)
...
Lots and lots of it..
...
2007-02-28 10:41:35 EET - postgres FATAL:  sorry, too many clients already
2007-02-28 10:41:35 EET - postgres ERROR:  deadlock detected
2007-02-28 10:41:35 EET - postgres DETAIL:  Process 41021 waits for
AccessExclusiveLock on relation 965687 of database 16398; blocked by
process 41071.
        Process 41071 waits for AccessShareLock on relation 965684 of
database 16398; blocked by process 41021.
2007-02-28 10:41:35 EET - postgres CONTEXT:  SQL statement "REINDEX
TABLE category_tree"
        PL/pgSQL function "update_itemcount" line 48 at SQL statement
2007-02-28 10:41:35 EET - postgres STATEMENT:  SELECT * FROM
update_itemcount();
2007-02-28 10:41:35 EET - postgres ERROR:  current transaction is
aborted, commands ignored until end of transaction block