Gain a bunch of Belief so you can spend 50 of it on boosting their Civilization soon?
More seriously--how about: their homes bear a striking resemblance to birds' nests (weaver birds, maybe, since they have roofs) and have to be rebuilt every spring. Since they're made mostly of materials one finds *in* the trees, it's not all that difficult for them (though cooking hearths would be tricky, I suppose). The "nomadic" part would just be the recognition that it's easier to find the materials (and suitable crotches of tree branches) if you move to a different tree when you do so. They're not necessarily fastmoving, wide-ranging nomads like the Mongols or the Plains Indians--their "nomadism" could be a fairly slow migration from tree to tree, moving only a hundred yards a year or so.
Would that work for everyone?