Os drivers AMD (Catalyst e fglrx) que estavam disponíveis nas versões anteriores do Ubuntu não estão mais disponíveis no 16.04. Isto é devido ao mau suporte da AMD para os drivers do Linux. Somente o driver de código aberto pode ser usado.
Eu tenho que ser corrigido se alguma forma alternativa for conhecida para instalar drivers AMD.
A placa gráfica AMD suportada pelo driver AMDGPU está listada neste link (para o Ubuntu 16.04 veja a coluna 15.10): link