Você tem duas opções. Faça downgrade para 14.04 ou instale os drivers AMDGPU / ATI de código aberto.
Foi assim que instalei os drivers da AMD no meu Ubuntu 16.04 Xenial
Faça o download do AMDGPU-PRO de aqui
Execute os seguintes comandos no terminal
tar xvzf amdgpu-pro-16.40-XXXXXX.tar.xz
cd amdgpu-pro-16.40-XXXXXX
chmod +x amdgpu-pro-install
sudo ./amdgpu-pro-install
Substitua XXXXXX pelo número de compilação. Finalmente, emita o seguinte comando óbvio.
sudo reboot
Para verificar se ele foi instalado com êxito, emita dpkg -l amdgpu-pro
Fonte: link