When you want to use Debian/Ubuntu just use my script.
In theory it should have worked, maybe you hd fglrx preinstalled and switched with
update-alternatives --config gl_conf
before, you have to repeat this or you have to uninstall fglrx and reinstall from scratch (thats the way i use in my script, feel free to use it if you also want to use .36 kernels). When you installed it on a pure install you usually don't use radeon with kms anymore so you might have just forgotten to use:
rm -f /etc/X11/xorg.conf*
aticonfig --initial --nobackup
Feel free to use "sudo -i"