That's a different situation. They are Ukrainian citizens. There were no Palestinian citizens before because there was no state there, neither Israel nor Palestine.
There was land there, they and their ancestors inhabited it for countless generations before present, so they must be considered legitimate citizens, regardless of the names it had back then or today. There was no modern countries in Americas before Europeans arrived, yet we don't call amerindians foreigners because of that.
States are not necessary for populations to exist or thrive. Politically homogenous states united under a defined hierarchy is a new phenomenon; and much newer than the discovery of agriculture.
