vacuum issues under load?

We have recently discovered a problem with our slony-1 cluster of 8.1.19
installs. Specifically, we are unable to vacuum a table on the master
node; vacuum always hangs on the same index of the same table. If we do a
slony switchover and make the other node the master, then *it* will become
unable to vacuum that index. Vacuum on the slave always works quickly and
without issue. Vacuum does not hang anywhere else.

When we tried to strace the vacuuming backend, it appeared as if it was
trying to acquire a lock, but pg_lock showed nothing unexpected for that
index. We can also manually acquire an access exclusive lock on the
offending table if we desire. FWIW, we have about 1,000 sessions, and
while most of them are idle, we still average a couple hundred queries/s.
The index in question is a simple unique btree over a column of type
character(40).

Has anybody else experienced anything like this? We are hoping this
problem magically goes away when we upgrade to 8.4 next month, but it
would be great if we could solve it before then.

Thanks for any suggestions....