Os drivers AMD exclusivos não são oficialmente suportados no 16.04. É recomendado que você use um Ubuntu anterior.
No entanto, você não deve usar o 15.10, já que não é uma versão LTS. As versões LTS recebem atualizações de segurança por cinco anos. As versões não-LTS recebem atualizações de segurança por nove meses. 15.10 deixará de receber atualizações de segurança no final deste mês.
Use 14.04 LTS. É suportado até 2019.