I know when I have reinstalled fglrx I have usually done what you have done
but slightly differently as I have usually had to go back to the open source versions for a while.
I found this guide to be really helpful
Ati Ubuntu Wiki
However this worked for me last time and got rid of pretty much all of the ati/fglrx stuff left on my pc
sudo /usr/share/ati/fglrx-uninstall.sh # (if it exists)
sudo apt-get remove --purge fglrx*
As a further measure I also check what else is left
dpkg -l '*fglrx*'
and
locate fglrx
I also make sure I have a correct set of open source drviers installed
sudo apt-get remove --purge xserver-xorg-video-ati xserver-xorg-video-radeon
sudo apt-get install xserver-xorg-video-ati
sudo apt-get install --reinstall libgl1-mesa-glx libgl1-mesa-dri xserver-xorg-core
sudo dpkg-reconfigure xserver-xorg
I then rebuild the the proprietary fglrx/Catalyst driver to be installable through the Restricted Hardware Driver Manager (a.k.a. jockey)
sudo apt-get install fglrx-modaliases
After these have all been completed I reboot and now the open source drviers are working AND xserver-xorg has bene rebuilt I reinstall fglrx
sudo apt-get install fglrx
That seemed to do the trick last time.
Let us know how you get on
After using amdcccle to set the monitors as required, apply and exit, then from System -> Preferences -> Screen Resolution [or Monitors in Debian], verify it is showing the resolution you configured in amdcccle and click apply.
The next time you restart or login the settings will be preserved.
Best Answer
Just run
amdcccle
from terminal, you can also make a shortcut, to run as root usesudo amdcccle
.