O Ubuntu 16.04 não suporta os antigos drivers FGLRX da AMD. Eu tenho placa gráfica GCN 1.0 e não posso executá-lo no Ubuntu também. Eles até empurraram uma nova atualização em 14.04, onde o FGLRX não funciona mais. Não sei se sua placa gráfica é GCN ou não. Se não for GCN, esqueça o Ubuntu. Vá para outras distribuições Linux como o Linux Mint 17.3 para FGLRX.
Editar: Acabei de verificar se a sua GPU é TeraScale 3 e não GCN. Você não tem outra opção a não ser ir para uma versão mais antiga da distribuição Linux, que não é o Ubuntu. Experimente o Linux Mint ou tente o site do DistroWatch.com para encontrar uma distribuição Linux para o seu computador. Além disso, você pode querer substituir sua GPU com a mais recente / mais recente placa gráfica.