Updating the map mid-game with Wrye Mash will do this, There isn't any real fix, I don't think.
But it shouldn't affect New Games.
But what do you mean that your new map is screwed-up except for map markers being messed? That's all that is wrong with this map.
Also, you can get rid of the Map Grid by simply turning it Off in Mash.
OFF? i turned it on? lol, how?
and on my older save all those yellow squares that represent a "place" had appeared, even though i hadn't been too them.
EDIT: @metalfiend00, http://planetelderscrolls.gamespy.com/View.php?view=Mods.Detail&id=6147
EDIT: @pluto, notice where i am on the map?