It becomes a lot less complex if you are just making changes to the existing map. All that actually changes on the "map" part is the boundaries. These can be redrawn quite easily. If you want to change names, change terrain type etc, that is all done in the txt files. So if you wanted Wales to be called Cymru (which would be perfectly reasonable) then you'd simply edit the "region_specific.txt" and startpos files.

In each startpos file find the SetRegionAttribute:: line for ID_WALES, change the name where it says "Wales", to "Cymru" and "Wales_castle_xzy" to "Cymru_castle_xzy", then make matching changes in your region_specific.txt file. Everywhere you find Wales, replace it with Cymru and your province will now have its new name. If you want to change the terrain, simply edit the SetBorderInfo:: lines in the startpos files.

If you want to change the BORDERS of Wales, so they get the Marches back, for instance, but keep everything else the same, then that is a simple graphics job.

The really functional bit is the LUKUP.LBM map in the textures/campmap folder. (The original MTW has four copies, two large, two small - you only need TWO copies - one large, one small - compare with the textures/campmap/Viking folder)

First off you need to convert this to another format to work on. Either UltimatePaint or Mithel ImageConverter are needed here (there are others but I'll stick with the easier ones). UP can convert it to BMP format (IIRC), which is best, Mithel outputs in either JPG, PNG or LBM. It's best to get the LUKUP into BMP 256 colour format, with the correct palette. Open this in Photoshop or whatever, and then simply redraw the area of Wales using the correct colour - each province has two colours - a body colour and an outline colour. When you're happy with the re-absorbed Herefordshire, say, then save to 256 BMP, then double the size and save again as LUKUP2. Convert these two back into LBM format using Mithel (this is simply the best tool for this job), copy back into your textures folder and give it a go...

If you really want to go to town you can also grab BIFReader and change the borders on the minilukup and fe_minilukup maps, but something so small is probably not worth the bother ...