Thank you all for your comments. This should be pretty close from the final version : http://warlight.net/SinglePlayer.aspx?PreviewMap=23358
I removed the blackwater bridge connecting The Reach and the Riverlands to give both these bonuses a break, as suggested
As for the Bone mountains, they are already split between the Jhogos Nhai and Yi Ti in the scenario distribution, because they would indeed be a terrible starting position.
I'm affraid a North-South connection is not really possible for this kind of projection map.
I also lowered the bonuses at n-1 armies on land and n armies on sea. Land bonuses have the second, larger bonuses to compensate.
For the scenario, Sea nations (Braavos, Iron Islands, Ibben, Summer Islands) seemed to be underpowered, being true glass canons, so I completely reingeneered the sea territories to make them more defensively reliable. There are now more sea territories and less ports.
Since I changed that quite a bit, their might be a few connections mistakes there, but land connections should be fine at this point