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(at)dsrich(dot)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.