If you have installed the Graphics drivers through the software center or the 'Additional driver' button in system settings I would suggest to reinstall them using the newest driver package from the amd website.
It's a pretty straight forward process and done very quickly through the terminal, just copy and paste every command I put here.
sudo apt-get remove --purge xorg-driver-fglrx fglrx*
sudo apt-get remove --purge fglrx*
sudo apt-get install build-essential cdbs fakeroot dh-make debhelper debconf libstdc++6 dkms libqtgui4 wget execstack libelfg0 dh-modaliases
sudo apt-get install --reinstall xserver-xorg-core libgl1-mesa-glx libgl1-mesa-dri
sudo dpkg-reconfigure xserver-xorg
These commands remove the previously installed drivers and make sure all the dependencies for the new drivers are included.
These next ones download and activate the driver installer script from amd
sudo chmod +x amd-driver-installer-12-3-x86.x86_64.run
sudo sh amd-driver-installer-12-3-x86.x86_64.run --buildpkg Ubuntu/oneiric
sudo dpkg -i *.deb
The graphical amd installer will now guide you through the driver installation (just as it would in windows for example)
After it's done just type
sudo aticonfig --initial
Now reboot your system and see if the issue is resolved.