O mesmo cenário exato para mim. Tentei um monte de coisas, então algo finalmente funcionou. Na inicialização, selecionei as opções avançadas: Repare os pacotes, ele fez algumas coisas até travar e apertei ctrl + c então continuou com erros, depois disso precisou de um ctrl + alt + del e reiniciou.
O sudo apt-get install atualiza e o sudo apt-get distro-upgrade mostra que os drivers serão removidos. Ele removeu e eu reiniciei, mas não conseguia logar (devolvido para a tela de login) Talvez aqui você pode fazer sudo chown username: username .Xauthority para consertá-lo, mas eu não sabia sobre isso ainda assim eu fiz alguns outros comandos antes fazendo o comando chown (que corrigiu meu problema de login e tudo está bem) Então, após o comando distro-upgrade eu fiz sudo apt-get purge amd * instalei o driver de 16.40 amd novamente reboot
Não sei por que funcionou, mas talvez isso também ajude você. Boa sorte