I've been following this map with some delight, I think this will be a charming historical map with some polishing

After some study, I think I see all of the gameplay elements clearly and I don't see any major conceptual problems. Good job! I have only one question- is this a conquest map or is it open deployment or some combination of open and neutral regions?
However, it did take me a little bit to sort out the gameplay- as you seem to be aware, the legend wording will need a fair amount of work. Also, I would keep the striped/different color look to the lands, it helps make this map clearer and as Jatekos said helps distinguish the icons.
There simply will have to be more space provided for the army numbers too. Use 888s- if you can fit those in, there should be plenty of room.
As for the English in the legend, I have some suggestions which might preserve the flavor while making more room on the map.
For the title, I think you could put the year 1301 A.D, and save some space- the title needs to be shorter anyway. Something like:
"The Hungarian Oligarchy- 1301 A.D." (the word 'Oligarchy' already has a Medieval flavor, so I think that we can take out the work Medieval. Also, '1301 A.D.' is by definition in the 14th century.)
For the history, then, here's what I've got:
"The King of Hungary, last of the Arpad dynasty, is dead.
The Kingdom waits for a new ruler. Three foreign candidates have split the land between powerful nobles- the Oligarchs.
They fight to gain more power and bring his favourite to the throne."
For the losing condition and victory objective:
"My Lord, control all Royal Castles for one turn to end this bloody war.
Beware my Lord; if your Oligarch Castle falls, all is lost."
The gameplay part of the legend I'll need to think upon a bit. I can't help but think that you can lose the bridge icon and simply put a bigger Town/Castle icon on the river directly, but then you'll have to indicate which region will work for the bonus.
Marshal Ney