No one is saying that all citizens are natural born citizens. Schwarzenegger, Granholm, and Kissinger are not eligible because they are not natural born. All three were born citizens of other countries (Austria, Canada, and Germany, respectively) and only later became American citizens through naturalization.
All who were born citizens, however, are natural born.
In Wong Kim Ark, the Court appealed to the tradition of English common law:
It thus clearly appears that, by the law of England for the last three centuries, beginning before the settlement of this country and continuing to the present day, aliens, while residing in the dominions possessed by the Crown of England, were within the allegiance, the obedience, the faith or loyalty, the protection, the power, the jurisdiction of the English Sovereign, and therefore every child born in England of alien parents was a natural-born subject unless the child of an ambassador or other diplomatic agent of a foreign State or of an alien enemy in hostile occupation of the place where the child was born.
Very like the 14th Amendment, isn't it? Wong's parents were illegals from China. One of Obama's parents was an American, and the other (assuming he wasn't Frank Marshall Davis) was a legally authorized visitor. But if Wong had had the political mojo to run for president, he would have been eligible.
Nope. They were both legal residents.