I haven't played 1.0 in ages so I'm not sure what to make of this. You should check and make sure your king isn't trapped in some "land-locked" province. That could cause loyalty to drop. Anyway, I heard those Saharan people in Cyrenacia love to raid farms and kill peasants.