Поле с автоинрементом должно иметь либо уникальный индекс, либо быть первичным ключом (также будет иметь уникальный индекс).
ALTER TABLE `table`
ADD UNIQUE KEY `field` (`field`) /* или ADD PRIMARY KEY `field` (`field`) */
ALTER TABLE `table`
MODIFY `field` int(11) UNSIGNED NOT NULL AUTO_INCREMENT, AUTO_INCREMENT=последнее значение поля + 1
То есть значения поля на момент добавления индексов должны быть уникальны, и нужно знать последнее значение, чтобы его + 1 подставить в запрос.
PS.
из-за того, что индексы уже идут не поп порядку? - в базе вообще в навал все, а индексы хранятся отдельно, а что касается значений, то уникальный с автоинкрементом означает, что некоторых значений вообще может и не быть, удалены, и они больше базой использоваться не будут.