The amdcccle app is part of the ati proprietary driver. Factor in the deprecation of relatively current video cards (HD4xxx). And things get a lot less intuitive. I'd recommend booting to console and using startx to start your gui environment. Until you have functional fglrx drivers (ati's version). Beware that ati replaces libGL for openGL things. Use dpkg-divert to inform you a bit on this if you're using a debian package method to acquire your driver.
I don't know if this is the current state of things but I installed the ati drivers(12.6) with a non-distro package method (Debian/sid). And it did NOT build the fglrx kernel module. Which is hinted to in the log file the install generates. But not really notified with anything that says, but wait, there's more. Perhaps that's the issue you're trying to overcome. In either case I'd recommend uninstalling any display manager until it's resolved (gdm, kdm, xdm, wdm, ???), aka no graphical login. Or just avoid it and use the radeonhd or radeon or vesa driver.