Appreciate you putting up the Q&A Thoram...
Following on from both Skjuludde & Telenil about the naming of towns & castles:
Leave the campaign as it is, its in HvH and multiplayer that we want the names of places - so that leaves 2 options on how to fix it for us:
1. Pick a set date for all Hvh and Multi games, as Skjuludde has suggested the time just prior to the War of the Usurper/Roberts Rebellion is perfect as all Houses will be positioned in the same locations as you currently have them.
With the date set, give each of the Feudal Homes their correct names at that date. This does not affect the lore or storyline of the books, so there is no license being impinged upon.
For each of the castles & towns, give them a name of the closest approximate town or castle to their on map location. This keeps the map balanced as you intended but provides some immersion for us players. Hell, you could even ask the forum what name should be given to each location so the decision making is taken out of your hands

2. Provide an editable label for each structure in the game that can show the generic structure name (Town 1, Town 2, Eastern Castle, Ruin A, etc). This will allow players to put the names of towns etc in themselves and will not affect the AGOT/GRRM licence.
In terms of giving our units & characters names, the House you select already has the main family surname, so all that is needed is some randomly generated first names to go with the family name of the House and that would fix the issue.
In terms of showing other reknowned castles & structures such as Harrenhal, the Twins, Dragonstone, the Hightower @ Oldtown, including these would actually make it easier to read the map as you'd have easily identifiable landmarks that would tell you exactly where you are.
A simple gameplay mechanic to add to these types of structure could be something as easy as extra prestige for taking control of them, say 10pts for each structure. There inclusion would be similar to the current struggles that go on for ruins & septs in the game currently.
You could also easily add benefits such as decreased cost of some units, increased unit abilities etc that would tie in with the theme of AGOT, for example:
Control
Harrenhal - decreased cost of Mercenaries (tie in with the lore: has a history of switching hands & being controlled by mercenaries & turncoats)
Control
The Twins - increased envoy ability (tie in with the lore: controlling the crossing gives you stronger negotiating power)
Control
Dragonstone - increased guardsmen ability (tie in with the lore: as the seat of the Heir's apparent of Westeros, Dragonstone is well used to providing the best guardsmen in the land)
Control the
Hightower @ Oldtown - increased Merchants yields (tie in with the lore: as one of the greatest ports in Westeros, Oldtown is a centre of trade & home to the most experienced merchants)
These could be further added to with unique structures for other examples such as Moat Cailin, White Harbour etc.
Another idea would be if the prestige titles in HvH and multi be renamed to give more of a theme aswell? The factors to gain them would remain the same but could be changed better to fit with the lore, to something like the names of the small council members perhaps?
1st Title - Form Most Alliances ...
becomes: Master of Laws
2nd Title - Create Most Victims ...
becomes: Master of Whispers
3rd Title - Earn Most Income ...
becomes: Master of Coin
4th Title - Control a Sept ...
becomes: Grand Maester (best fit???)
And instead of offering 3 titles for 3 houses each controlling a Sept, could it be changed to the house that controls Most Septs and then create a further 2 new titles available?
Example:
4th Title (revised) - Control Most Septs ...becomes: Grand Maester
5th Title (new) - Assemble Largest Army ...becomes: Lord Commander of the Kingsguard
6th Title (new) - Control Most Regions (towns, castles, farms) ...becomes: Hand of the King
And my last point/question - what chance of including House Greyjoy in the game?
I know sea-faring is not possible in the game (currently or ever?) but they could be included with the Iron Islands set as their Feudal Home (ofcourse) and have a simple simulated sea-crossing (that anyone can access) to lands at The Neck that would put them in direct competition with House Stark for resources in the north.
On the Westeros map House Stark are currently isolated in the north and can get a head start quite easily in HvH games as they and their towns/farms/castles are that bit more removed from the other House's.
Anyways, thats my lot for now atleast.
EDIT: Or if none of the above is possible, could you open up the game to modding or release some sort of toolset that allows us to make changes & additions ourselves?
It would lengthen the lifespan of the game (see what it has done for Medieval Total War II, which still makes sales) and tie the community closer to you for interest & opinion on potential future releases. A happy community = positive opinion & good word of mouth = more sales over greater period = happier Cyanide