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=#