O FGLRX foi preterido em 16.04, e acho que a AMD está migrando para uma pilha de drivers abertos.
Se você tem um pouco de google por "fglrx em 16.04" você deve encontrar alguns relatórios sobre isso com bastante facilidade.
Então, no momento você está sem sorte!