I had a similar issue. The issue was the table had a record with ID = 0 similar to what SystemParadox pointed out. I handled my issue by the following steps:

Steps:

1. Update record id 0 to be x where x = MAX(id)+1
2. Alter table to set primary key and auto increment setting
3. Set seed value to be x+1
4. Change record id x back to 0

Code Example:

UPDATE foo SET id = 100 WHERE id = 0;
ALTER TABLE foo MODIFY COLUMN id INT(11) NOT NULL AUTO_INCREMENT;
ALTER TABLE foo AUTO_INCREMENT = 101;
UPDATE foo SET id = 0 WHERE id = 100;