Como você não declarou, vou assumir que você está instalando o Ubuntu 16.04 LTS com o kernel 4.4 e está tentando usar o driver AMDGPU-Pro em vez do driver de código aberto AMDGPU, que deve ser carregado por padrão o kernel. Se este for o caso, eu reinstalaria o Ubuntu. Certifique-se de que você está usando o kernel mais recente. O Ubuntu 16.04.3 deve estar usando o kernel 4.10 se você tiver um kernel anterior, você precisa instalar o Hardware Enablement Stack (HWE) seguindo estas instruções. Depois de atualizar para a última reinicialização do kernel e verificar qual driver está instalado:
lspci -k | grep -EA2 'VGA|3D|Display'
Isso deve indicar que o driver do kernel em uso é "amdgpu". Se isso não acontecer, aguarde uma resposta melhor, mas se isso acontecer, você pode prosseguir com a instalação do driver proprietário amdgpu-pro seguindo as instruções da AMD. (Note que o driver proprietário fglrx não é suportado no Ubuntu 16.04)