Why does my table hold duplicate primary keys?

Question

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