Following the previous post about problems with ATI drivers, amdcccle (see it here), I' ve looked it into a little bit more.
I was lucky since guys at osarena.net (they rock), had the solution ready for me.
New ATI catalyst 11.8 to the rescue and a proper easy how-to.
This is basically a re-post of the one found in osarena.net (check it here) from the noobie perspective.
First download the new drivers from here. (I got the 64bit one)
Put the ati-driver-installer-11-11-x86.x86_64.run file in a folder (lets name it ati in the home folder) and make it executable.
$sudo chmod +x ati-driver-installer-11-11-x86.x86_64.run
$sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev*
Install the new packages (overwriting -f)
$sudo dpkg --force-overwrite -i *.deb
Create the xorg.conf file
$sudo aticonfig --initial -f
After the reboot, when you log in, you might receive an error message that previous settings could not be restored.
Thank you again osarena.net guys.