Eu tive o mesmo problema e resolvi-o seguindo as instruções desta página . A página está escrita em espanhol, mas todos os comandos estão em inglês, então é bastante simples.
De acordo com esta página, há um bug no script de instalação do Ubuntu / wily AMD. É por isso que você não pode instalar o novo driver.
Só para avisá-lo, o comando
sudo ./amd-driver-installer-15.30.1025-x86.x86_64.run --buildpkg Ubuntu/wily
pode levar alguns minutos para terminar, então não pense que o terminal está congelado.
E também há um pequeno erro no comando
sudo dpgk -i *.deb
O comando correto é
sudo dpkg -i *.deb
Espero que ajude!