MySQL - Unable to Convert Primary Key to Auto Increment
Your post intrigued me. There is a "workaround" here, but I was curious, so I performed the following tests. You might like to try what worked for me below before trying the workaround. If there are FOREIGN KEYs, and potential conflicts (duplicates and/or KEY violations), then this won't work. It may be the reason for your error.

I created a table (bill) as follows.

mysql&gt; CREATE TABLE bill(fred INT, paul VARCHAR(10));
Query OK, 0 rows affected (0.31 sec)


Then inserted some sample values.

mysql&gt; INSERT INTO bill VALUES(1, 'adsfd');
    Query OK, 1 row affected (0.05 sec)

mysql&gt; INSERT INTO bill VALUES(2, 'adsfd');
Query OK, 1 row affected (0.05 sec)

mysql&gt; INSERT INTO bill VALUES(3, 'xxxx');
Query OK, 1 row affected (0.05 sec)


I then performed a SHOW CREATE TABLE My_Table\G (the \G gives clear output that can be cut and pasted).

mysql&gt; SHOW CREATE TABLE bill\G
*************************** 1. row ***************************
       Table: bill
Create Table: CREATE TABLE `bill` (
  `fred` int(11) DEFAULT NULL,
  `paul` varchar(10) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)


Just to see the results of my INSERTs

mysql&gt; SELECT * FROM bill;
+------+-------+
| fred | paul  |
+------+-------+
|    1 | adsfd |
|    2 | adsfd |
|    3 | xxxx  |
+------+-------+
3 rows in set (0.00 sec)
mysql&gt; 


Now, issue your ALTER TABLE statement.

ALTER TABLE bill MODIFY COLUMN fred INT AUTO_INCREMENT NOT NULL PRIMARY KEY;

Recheck the definition of your table.

mysql&gt; SHOW CREATE TABLE bill\G
*************************** 1. row ***************************
       Table: bill
Create Table: CREATE TABLE `bill` (
  `fred` int(11) NOT NULL AUTO_INCREMENT,
  `paul` varchar(10) DEFAULT NULL,
  PRIMARY KEY (`fred`)
) ENGINE=InnoDB AUTO_INCREMENT=4 DEFAULT CHARSET=latin1
1 row in set (0.00 sec)


And the field fred is indeed now a PRIMARY KEY and also an AUTO_INCREMENT.

And to check that it's working.

mysql&gt; INSERT INTO bill (paul) VALUES('yyyy');
Query OK, 1 row affected (0.08 sec)

mysql&gt; SELECT * FROM bill;
+------+-------+
| fred | paul  |
+------+-------+
|    1 | adsfd |
|    2 | adsfd |
|    3 | xxxx  |
|    4 | yyyy  |
+------+-------+
4 rows in set (0.00 sec)


So, it's also AUTO_INCREMENTing correctly. I'm not sure why your original statement gave the strange ALTER TABLE causes auto_increment resequencing error - maybe a bug of some sort? While performing these tests, I made a number of small errors - MySQL appears to be very fussy about the exact order of steps and the particular syntax of the ALTER TABLE statement.