Bueno... puestos así, es imposible saber que pasa. No comentas siquiera cómo es que generas los nuevos valores para la llave primaria, ni has puesto un trozo de código que lo aclare.
¿te basas en un generador?
Si es así, pues alterá el valor del generador para que parta del primer número válido para la clave primaria y problema solucionado.
Hasta luego.
