Você está passando o primeiro parâmetro como um string quando usa aspas. Quando eu vou utilizar um campo auto-incremento, sempre defino 0 (zero) ao campo. Exemplo: $query = mysql_query("INSERT INTO teste VALUES(0,'$nome')"); Comigo isso nunca deu problema. Não sei se é a forma certa de se resolver isso, mas funciona.