What makes it tough is that a colony needs 1% bureaucrats from your primary culture, which can be tough to achieve. The rule of thumb is that the population of the protectorate needs to be at least 5% primary culture before it can reasonably be expected to achieve the 1% bureaucrats figure. For a large pop state in Asia/Africa, that's near-impossible.
As an example, as Two Sicilies I had conquered the Nile Valley and expanded into some of the Sahara last game. The Sahara regions practically turned into full states with minimal effort, and they quickly became Sicilian cores, with populations of up to 75% South Italian, because no one else lived there. Upper and Middle Egypt, with about half a million each, became full states in time, and were very valuable as decently-sized lands. Lower Egypt and Sinai, on the other hand, each had close to a million Egyptians and never became states throughout the entire game.