Wait until Ubuntu 16.10?
Summarizing the info online: (from Phoronix)
"The last release AMD did can not be used because it is incompatible with the newer x.org version 1.18 display server. Switching distros will be of no help. X.Org Server 1.18 does bump the video ABI so that means the proprietary graphics drivers will need to see new releases... If you're using the NVIDIA Linux driver you're in good shape while AMD Catalyst users will need to wait for a new release, which could be a while considering the upstream driver still doesn't support the latest Linux 4.x kernel releases without third-party patches."
AMD's Tim Writer commented in our forums that Ubuntu 16.04 won't be supported at all. "For those who don't know, I manage AMD's open source graphics team. We (AMD) are focusing our Linux graphics driver development on the amdgpu based open source and upcoming hybrid stacks; consequently, we are not supporting fglrx on Ubuntu 16.04 LTS. Users who require Pro-graphics or Workstation class features and performance can continue to use fglrx on Ubuntu 14.04 until the hybrid stack is available later this year."
Problems with the new driver code: