Thing is the Bedouin who have remained nomadic pretty much ignore those countries borders* and move around the whole area (seriously I've met them as far up as Syria). So while yeah OK there's more to being Bedouin than being Nomadic (and more to being Rom than being nomadic, so neither lose their cultural identity completely if they stop moving) it doesn't mater what they're called it's the behaviour that matters and they have to became sedentary to form a static country around themselves.
The other way to go is to have a county that large enough to encompass their movements, but frankly that kind of space tends to only really be available in central asia (and even then there is nomadic trans-border movement)
The only realistic alternative is the Sami solution in Scandinavia (who are basically semi-nomadic: they have their solid winter quarters and live nomadically half the year), who have their own cultural autonomy without a territorial autonomy; they can build their own school system, elect their own parliament which then represents them with the Finnish, Swedish and (IIRC) Norwegian government, etc. They are freely ranging across the borders (here, too, the increasingly more fortified Russian-Finnish border is a big thing). But they, too, suffer massive population drain into a more secure sedentary lifestyle.
The thing is that - the whole concept of a modern state, with all cultural and physical infrastructure, is antithetical to nomadic lifestyle. Not only do the nomads in a populated area compete with the sedentaries for resources, but the sedentary society competes with the nomadic society as a lifestyle decision. There are very good reasons why sedentary lifestyle nearly always wins out, it fulfills the material needs of people better than nomadic one. Caravan romantics are only attractive if you have full stomach and know where you will sleep safely this evening. And most nomads understand this very well.