Hmm, just a thought, but does your game utilize texture compression? (I recall the earlier GeForce cards had this issue with games that didn't use precompressed textures and could be fixed with a simple registry hack, and as you can guess, heavy compression with an inefficient algorithm/method can degrade texture maps to the point of looking like good old 8-bit)
As stated before, use Driver Cleaner to clear out any old entries of the driver and then reinstall, preferrably the Catalyst 5.12s if you haven't used them already. However, I'd like to note that Driver Cleaner CANNOT purge out every single trace left by the previous driver (e.g. stray registry entries), but it is usually the best start.