I would like to see the Marches split into
Cheshire (Chester)
Gloucestershire (Gloucester)
Shropshire (Shrewsbury)
Herefordshire (Hereford) - maybe combine with Glou/Salop
Pembroke (Pembroke/Carmarthen)
Cheshire was so important I wouldn't combine it with Shropshire. For the early part of the period (until just before 1300) the Marches were a significant power base. The greatest lords mostly came from the marches (Rupert fitzHenry (Glou) (brother to Maude), Both regents for Henry III (Chester/Pembroke), The regent for Edward III(Glou), ...). One of the sources for their power was the need for armed men to be ready to act at short notice, and the other was the fact that the lords on this border extended their influence beyond what their Kings anticipated.
And for Wales
Pembroke (West Deheubarth, east part should be in Gloucestershire) - mentioned above, for most of the period it was controled by Marcher lords
Gwynedd (Aber/Bangor)
Powys - Maybe split into Upper/Lower Powys (Lack of cities, could use castles, but they were build after 1066)
Powys was the largest and most significant part of Wales. The "princes" in Gwynedd only became pre-eminent within Wales when they conqured significant parts of (Upper) Powys. Upper Powys was closer to the coast and contained Mold, lower Powys contained Caus and should stretch to the edge of Cardigan/Carmarathen.
Spliting Wales into 4 provinces should be done by spliting the Powys rather than Deheubarth, both because of its size and because of its relitive importance.