Observa:
http://dev.mysql.com/doc/refman/5.0/...ric-types.html
El tipo de dato que usas para tu ID (autoincremental) es un TINYINT .. dices que tenga de longitud "5" digitos .. pero ese tipo de campo numérico no llega a más de "3" por definición ..
Además .. si no defines que sea "sin signo" su rango es -128 a +127 .. por ende como tu das "ID's" positivos .. si bien un "TINYINT" podría dar hasta 255 .. de esa forma sólo puedes usar 127 (más o menos el n° de registro que te daba problemas).
La solución es que leas bien sobre Mysql y sus tipos de datos. Usa un INT (o menor) pero "sin signo" para tomar de 0 a +4294967295 (registros máximo) y no la mitada si indicas que sea con signo. Creo que con esos 4 millones de registros ya tendrás para un largo tiempo XDD
Un saludo,