Existem algumas coisas que você pode fazer: 1) tente uma nova instalação do Ubuntu 16.04, se você não fez isso (atualizar sem limpar todos os dados pode causar problemas) 2) tente usar o driver radeonsi ao invés do amdgpu (eu li que o amdgpu é principalmente para placas AMD mais novas, como R9 380.285 etc)
Eu tive problemas semelhantes com a minha placa de vídeo AMD, tenho configuração de monitor duplo e, após a instalação, apenas um monitor funcionou. Depois de instalar os drivers fglrx, o sistema não apareceria. Eu tive que instalar o Ubuntu 14.04 e instalar os drivers fglrx no menu de configurações.
Então, se nada funcionar, talvez você tenha que voltar para 15.10.
Desculpe, sou meio novo no Linux, mas como ninguém mais respondeu, pelo menos tentei ajudá-lo com o que eu sei.