strange index error

i have the following, (bellow)

now each time i do an insert i get the error bellow,
i look at location_key_location_seq and see that the last_value has
increased,
from 11 to 12 to 13 to 14 extra..

this has happened before (not sure if it was on this table) and i had to
write
a script that just did a number of inserts until last_value was high enuf to
carry on inserts.
not good for a live database.

can any one hazed a guess as to what is happening or where to look,
the last time this happened we were on a sun Solaris box.
we updated postgres to 7.1.3 and have since (about 2 months ago) moved to a
Linux box, SeSu i believe.

wire_dev=# SELECT version();
version
---------------------------------------------------------------
PostgreSQL 7.1.3 on i686-pc-linux-gnu, compiled by GCC 2.95.2
(1 row)

wire_dev=#
wire_dev=# insert into location (building_key, floor, ref) values
(1,2,'SDFH');
ERROR: Cannot insert a duplicate key into unique index location_pkey
wire_dev=# \d location
Table "location"
Attribute | Type | Modifier

--------------+-----------------------+-------------------------------------
--------------------------
building_key | integer |
floor | integer |
ref | character varying(16) |
key_location | integer | not null default
nextval('"location_key_location_seq"'::text)
Index: location_pkey

wire_dev=# select * from location order by key_location;
building_key | floor | ref | key_location
--------------+-------+-------------+--------------
1 | 3 | 36 | 1
2 | 1 | I 23 | 2
2 | 1 | I 22 | 3
2 | 1 | I 21 | 4
........................................................
1 | 2 | DG18 | 126
1 | 2 | AG26 | 127
1 | 2 | AC26 | 128
1 | 2 | AE26 | 129
(127 rows)

wire_dev=#
wire_dev=# select * from location_key_location_seq;
sequence_name | last_value | increment_by | max_value |
min_value | cache_value | log_cnt | is_cycled | is_called
---------------------------+------------+--------------+------------+-------
----+-------------+---------+-----------+-----------
location_key_location_seq | 11 | 1 | 2147483647 |
1 | 1 | 25 | f | t
(1 row)

wire_dev=# insert into location (building_key, floor, ref) values
(1,2,'SDFH');
ERROR: Cannot insert a duplicate key into unique index location_pkey
wire_dev=# select * from location_key_location_seq;
sequence_name | last_value | increment_by | max_value |
min_value | cache_value | log_cnt | is_cycled | is_called
---------------------------+------------+--------------+------------+-------
----+-------------+---------+-----------+-----------
location_key_location_seq | 12 | 1 | 2147483647 |
1 | 1 | 22 | f | t
(1 row)

wire_dev=#
wire_dev=# insert into location (building_key, floor, ref) values
(1,2,'SDFH');
ERROR: Cannot insert a duplicate key into unique index location_pkey
wire_dev=# select * from location_key_location_seq;
sequence_name | last_value | increment_by | max_value |
min_value | cache_value | log_cnt | is_cycled | is_called
---------------------------+------------+--------------+------------+-------
----+-------------+---------+-----------+-----------
location_key_location_seq | 13 | 1 | 2147483647 |
1 | 1 | 21 | f | t
(1 row)

wire_dev=# insert into location (building_key, floor, ref) values
(1,2,'SDFH');
ERROR: Cannot insert a duplicate key into unique index location_pkey
wire_dev=# select * from location_key_location_seq;
sequence_name | last_value | increment_by | max_value |
min_value | cache_value | log_cnt | is_cycled | is_called
---------------------------+------------+--------------+------------+-------
----+-------------+---------+-----------+-----------
location_key_location_seq | 14 | 1 | 2147483647 |
1 | 1 | 20 | f | t
(1 row)

wire_dev=#