O Catalyst fglrx foi descontinuado para o Ubuntu 16.04. Ele usa apenas o software de versão gratuita amdgpu. Eu tive que voltar para 14.04 para usar o driver corretamente, porque minha placa de vídeo é uma R7 M200, e não é totalmente suportada pela amdgpu.
Você pode encontrar mais informações aqui