Why does my table hold duplicate primary keys?

To my big (and worrying) surprise I just realized that my table with millions of rows, has a few handful of rows, where the primary key (ID) is a duplicate! I don't understand how this can ever happen, and how I might prevent it in the future?

The column holding the primary key is, and has always been, subject to a CONSTRAINT fruits_pkey PRIMARY KEY(id);

I'm running postgreql 9.3.4 on ubuntu.

UPDATE

@Mat: Datatype is integer

@ypercube: Yes, select count() from (select count() from fruits group by id having count(*) > 1) as t1 returns 41.

@Craig: Yes, I have done a failover before, and my slave is actually 9.3.3

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!

StackExchange Database Administrators Q#62675, answer score: 6