Why does my table hold duplicate primary keys?

It was all caused by the bug described and fixed in this release: http://www.postgresql.org/about/news/1506/

It caused us a lot of trouble!