In my case, the problem was duplicate users. So, focusing on that, one way of finding them that worked well for me, was this:
SELECT username_lower, count(*) from users GROUP by username_lower HAVING count(*) > 1;
This gave me a list of the duplicates, with the count for each.
username_lower | count
----------------+-------
jagger | 2
richards | 2
patrick | 2
peter | 2
jagman | 2
(5 rows)
After fixing those, I was able to run a successful reindex, and after that, a successful rebuild.