Parece que meu problema é o mesmo, Não é possível instalar o fglrx ou computador de inicialização . Eu executei o comando /usr/share/ati/amd-uninstall.sh --force
no console de recuperação para remover completamente o fglrx. Então eu consegui fazer o login (usando o nomodeset no grub) e baixar o último driver da ATI do site da AMD.
E tudo funciona de novo, mas ainda fico com falhas gráficas de vez em quando, linhas correndo pela tela. É completamente tolerável, mas espero que alguém encontre uma solução para isso. Ele também mostra o driver VESA-REDWOOD em Configurações do sistema > Detalhes.