As dependências que ligam os pacotes Debian garantem que você não pode quebrar um pacote desinstalando outros, a menos que você force as coisas. Portanto, se o pacote gnome-control-center ainda estiver instalado, isso significa que todas as suas dependências ainda estão lá também.
Dado que o driver fglrx foi instalado a partir dos binários fornecidos no site da AMD, ele não tem a mesma garantia. Se puder, sugiro desinstalar fglrx com sh ./amd-driver-installer-[version]-x86.x86_64.run --uninstall e verificando se gnome-control-center funciona sem ele (usando o driver radeon ).
Uma vez determinado, você pode reinstalar fglrx , talvez usando os pacotes disponíveis junto com o Debian nos repositórios non-free (inicie no fglrx-driver , você pode precisar adicionar contrib e non-free às linhas que terminam com main em /etc/apt/sources.list ). Instruções completas estão disponíveis no wiki do Debian .