Eu finalmente resolvi o problema.
Não houve amdcccle ou fglrxinfo ou aticonfig mesmo após a instalação do fglrx
A razão para isso é que os arquivos executáveis essenciais não estavam lá nas pastas corretas. Então eu fiz isso fazendo alguns links como mostrado abaixo:
ln -s /usr/lib/fglrx/bin/aticonfig /usr/bin/aticonfig
ln -s /usr/lib/fglrx/etc/ati/ /etc/ati
Mesmo depois disso, aticonfig --inicial me deu erro
% bl0ck_qu0te%O seguinte comando resolveu o problema
/usr/lib/fglrx/switchlibGL amd
e, em seguida, reinicie