citizenship and presidency

Most Americans know that you have to be a natural-born citizen to become president. (Of course, the definition of "natural-born" is somewhat open to interpretation.) My question is this: are you eligible to become president if you are born outside the US (including its territories), but the place of your birth becomes a new state? And another: Do you retain eligibility if you were born on U.S. soil, but the location later became, somehow, non-US?

Wacky related question: If you are born on a plane flying over the US, does that count?

Finally, do any of you have thoughts about the idea that citizens who are not natural-born citizens cannot become president?

== != =

gah, I've been staring at the same piece of drek for an hour now. Maybe more. stupid "if" statement had = instead of == for the condition. Must have looked at it a hundred times and just didn't see it.