A couple of suggestions:
1. What about splitting KOJ into two - KOJ and the Principality of Antioch? KOJ is overpowered. This may add a little spices to this area.
2. What about adding the Papal States back in? This would represent all of Europe, but mostly the Kingdom of Sicily and the Italian States. All of these groups did a lot of attacking/raiding into Egypt, Greece and Anatolia. It you played as Byzantium or Ayyubids, they'd be someone to watch out for, that you couldn't attack (because Papal States respawns). It realize this could be a little problematic, and require testing, but worth bringing up.