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