I'm having the same issue as well. Was bearable at the start with only the smaller lines but now it's just blobs all over unless I zoom way out. I've noticed that the troops aren't there, only those lines in place of them.
Yes I have done as you asked above as well.
My error log if it helps:
[instanttextboxtype.cpp:92]: Not used, use maxWidth and maxHeight file: launcher/interface/main.gui line: 87
[instanttextboxtype.cpp:92]: Not used, use maxWidth and maxHeight file: launcher/interface/main.gui line: 104
[technology.cpp:718]: Missing Tech seed values:
[technology.cpp:755]: None.
[texturehandler.cpp:181]: Couldn't find texture file: gfx//coats_of_arms//dynasties4_muslim.tga.
[texturehandler.cpp:181]: Couldn't find texture file: gfx//coats_of_arms//dynasties4_indian.tga.
[texturehandler.cpp:181]: Couldn't find texture file: .