No sabía de este comportamiento de la llave primaria... aún así, es una situación poco común tener que alterar la llave de una tabla. Para esos casos, lo ya dicho por vos... copias de seguridad y quizás un volcado de la tabla a una nueva estructura resulte lo mejor...
Un saludo.