Thanks for the picture. It speaks a million words. I wasn't expecting what I saw from your written description! (Nice laptop, btw!)
And you're right - that looks very unusual. I've not seen it before (I have AMD 7870 desktop). But....
To me it looks like a shadows problem. Like you have "micro-clouds" casting tiny shadows on the ground. If you look at shadows of ground objects like trees and buildings, the effect is very similar. One building shadow in particular simply looks very jagged as it's shadow and the speckle effect mingle together.
You could try playing around with the HDR toggle and Shadows settings under graphics options (like, turn them off completely...). This is quick and easy and not disruptive, so I suggest trying this first.
Next up, are you sure the laptop is using the AMD card to play the game, and not the embedded intel graphics?
I have tried Lucid MVP, and CiM is a game it doesn't know about, so it will resort to using integrated graphics by default. But you can manually add the game exec to the games list, and set it to use D mode. Simply turning off Lucid probably won't work, because it will then ONLY use the graphics the machine booted with - which is most probably intel graphics, given you have a laptop.
EDIT: while I was writing this, I got the strangest feeling that in fact, I have seen this before. That CiM was the first game I played on my new machine with Ivy Bridge, 7870, and Lucid MVP. And that Lucid using integrated graphics for it was the problem. But my memory could well be playing tricks.
The AMD 7xxx range is a whole new architecture for them, and they're still learning how to write drivers for it. So, now more than ever, you really must try Drag0nflamez' suggestions and try a variety of graphics drivers. My 7870 desktop card has been somewhat unstable, and I settled on the 12.6 official release as being best so far. I've read that the 12.7 beta driver is a leap forward in performance, but when I tried it, I found system stability was very poor. It looks like the 12.6 release is presently the latest release for your mobile chip too.
You should completely uninstall any old AMD drivers first. And use Driver Sweeper to clean AMD drivers after the uninstall. DS can also store your desktop icon layout for later restoration, so do this first, as the desktop will be wrecked by the low resolution after windows resorts to vga clunk-o-vision.
Hope that gives you something new to go on.
