Instalar o Ubuntu 16.10 resolveu isso para mim. Começando com o 16.04, os drivers antigos da AMD foram substituídos pelos mais novos da AMD.
O Ubuntu 16.10 possui o kernel mais novo (v4.8) e, portanto, tem melhor suporte a gráficos para a AMD. O Ubuntu 16.04 vem com o kernel v4.4.
Como alternativa, você pode instalar o kernel mais recente do kernel principal do Ubuntu PPA - link e remover o nomodeset de grub.