Recently after my hosting provider hard-booted one of my machines the MySQL service started to complain “Failed To Read Auto-Increment Value From Storage Engine” when an insert was issued to any table with an auto increment field. I found the solution here, and it basically requires you to reset the auto increment key on the table, like this:

ALTER TABLE `table_name`  AUTO_INCREMENT =1

I had to do that on all of my tables that had auto increment keys to resolve the issue.