Do subsequent inserts take even longer? Maybe it's doing a full table scan for some reason - but even then that shouldn't take 40 seconds. But the only thing I know about MySQL is how to spell it (and I may even have the capitalisation all wrong) so who knows.
Does it have Oracle-esque 'Explain Plan' functionality that may give a clue?