I forgot to mention it in the commit message, but this patch
http://archives.postgresql.org/pgsql-committers/2006-05/msg00069.php
includes a fix to avoid "tuple concurrently updated" failures in
CREATE INDEX's update of the parent relation's pg_class entry.
I'm still not convinced that that's where your problem is, however,
because AFAICS that ought to be a pretty low-probability scenario.
If that fixes it for you then there's something pushing the system
to complete index builds at about the same time, and I don't see
what that would be.
regards, tom lane