Esta medio tarde la repuesta pero por si a alguien le sirve. Lo que yo hice fue crear una copia en otra tabla, luego vacío la tabla original (ojala se les ocurra sacar backup de pronto no es lo que querian) y hago un insert tabla(campo1, ... campo n) select campo1 .... campo n from nueva_tabla y de esta forma me ingresa los datos a la tabla inicial pero con la primary key ordenada. Obviamente que para hacer esta reorganización esta tabla no debe estar siendo usada como llave foranea de ninguna otra tabla.
