BUG #13507: INSERT into tables with SERIAL primary keys failing about half of the time

The following bug has been logged on the website:

Bug reference:      13507
Logged by:          David Richardson
Email address:      dsrich@dsrich.net
PostgreSQL version: 9.3.9
Operating system:   Ubuntu 14.04
Description:

Table:

CREATE TABLE payees
(
  payeenum serial NOT NULL,
  payeename character varying(127) NOT NULL,
  remarks text,
  CONSTRAINT payees_pkey PRIMARY KEY (payeenum),
  CONSTRAINT payees_payeename_key UNIQUE (payeename)
)
WITH (
  OIDS=FALSE
);
ALTER TABLE payees
  OWNER TO dsrich;
GRANT ALL ON TABLE payees TO dsrich;
GRANT ALL ON TABLE payees TO users;


Insert query:

INSERT INTO payees (payeename, remarks) VALUES ('some string', 'some other
string')

This query (and three other versions  using DEFAULT and 'RETURNING payeenum'
clauses) fails about half the time with payees_pkey constraint violation.

There is nothing else going on in the database server, and the failure
occurs both when the query comes through Npgsql (where I first saw this) and
through pgAdmin.

The same database has another table with the same basic structure that also
has the same problem.