If you envisions this nomadic movement as a straight line, of course that leads to some disconnect, but think of it as a circle or a general territory that the hold moves around?
I think that nomadic tribes circled a set of territory, you had your summer land, your winter land, etc, so there is the possibility of having them return to a place regularly, perhaps for supplies.
Also, there is the possibility of other tribes roaming the land.
Lastly, while it can be a good idea to really hammer the "yes, and..." in, be aware that you can go too far the other way. The players would like you as a part of the game as well, and if you know you need to set something in a certain way for the game to work, do not be scared to do so. Sometimes, in terms of improv, you need to make offers, strong choices.
As an analogy, I'm a psychology student, currently treating four patients. I definitly leaned towards following and encouraging my patients at first, and dreaded interrupting them. But a therapist that never would stand up for his knowledge and expertise, who would never direct his patient but rather let them remain where they were stuck wouldn't be much help. With experience, I've found a better balance between following and leading, between encouraging and challenging.