Before everyone gets on their high horse in regards to whether anyone should have ever have a valid reason for reseting an AUTO_INCREMENT counter, there are scenarios where it makes sense. A production db isn't the place for this, but development and QA environments are different.
I have created code to do this myself for Fixtures in a development environment, not to mention unit test databases that need to be repeatedly cleared. Sometimes you want to be able to truncate tables rather than doing a complete recreation.
It's a completely reasonable request, and there might be good reason for it, especially if you're counting bytes and making use of an UNSIGNED tinyint and similar byte optimization with some of your foreign keys.
As stated the solution is:
ALTER TABLE tablename AUTO_INCREMENT = 1
However, this will not work, if there are foreign key constraints defined.
The magic "get around fk constraints and other chicken-and-egg problems" that can happen with InnoDB constraints is:
SET foreign_key_checks = 0;
When things are zeroed back out the way you need them to be, you can then turn constraint checking back on with:
SET foreign_key_checks = 1;
This seems like it may be the actual issue the OP is having.