Ubuntu 16.04 LTSではRADEONドライバーが公式サポートされないらしい件

Ubuntu Drops Support For AMD's Catalyst GPU Driver - Slashdot
より、Ubuntu 16.04のリポジトリーからfglrxが削除されたらしい。
fglrx-installer package : Ubuntu
を見ると確かにxenial用のパッケージは存在しない。AMDが16.04に対応したドライバーをそのうち公開するかもしれないが、Ubuntu 16.04の正式リリース後しばらくは標準ドライバーを使わざるをえないっぽい。