I've been hit with the exact same problem on two different AMD64 machines running Trinity Radeon series 7000 cards (the HD 7540 and 7480D) on two different Ubuntu versions (13.10 and 13.04) in the same month! I'm sure I'm not the only one who has experienced this, but I haven't been able to find either solutions or, at the very least, other people with whom I can share my pain.
On both machines I experience flickering (among individual objects - not the whole display), screen regions being randomly shaded (in at least Firefox and LibreOffice Calc) and object drawing failures (the grid in a Calc document). These problems can be reliably reproduced.
Does anyone have any idea what's going on and how I can fix it?
Here's a screen shot: