On the same card/driver (5870, Win7 x64, Catalyst 9.11), I'm not seeing that trouble - so it's not pervasive to all 5870s.  I did see something similar after running the game for several hours (icons and textures went black), but think that was related to the game running out of memory soon after

I have same amount of memory - using onboard sound (vs CL), and AMD 940 (vs intel, still quadcore, though).  Other than that, looks similar.  Will restart a bunch of times and see if I get corruptions, too.

So I’ve found the actual culprit: It is an interaction between Elemental and Adaptive Multi-sample AA. This is a mode that can be turned on in the Catalyst Control Center and causes the card to perform antialising on transparent textures. However, when enabled, as it was on my system, is causes the map problems shown in my post. The solution/workaround is to either disable AA in Elemental, or to disable Adaptive AA in the CCC.

I am unsure if this is a game bug or driver bug, but you may wish to chat with ATi about it.