Depois de inicializar no modo de recuperação, você primeiro precisa ativar a rede.
Existe uma entrada de menu na mesma visão geral onde você seleciona a conta root.
Agora execute:
sudo apt-get update
sudo apt-get install -f
sudo apt-get purge fglrx