X.Org Server 1.18 landed in Ubuntu 16.04 a few days back. While X.Org Server 1.18 has been officially out since the end of 2015, the AMD proprietary driver was never updated to support this latest video ABI. (The Catalyst driver is also lagging behind on its official support for recent Linux kernel versions, albeit the community has partially been able to work around that.)
Any regular Phoronix reader will know that AMD has been investing heavily toward their new Linux driver architecture that centers around the open-source AMDGPU kernel driver. That new driver stack is coming out later this year, but in the mean time it appears rather clear now that it doesn't look like AMD will be maintaining the current Catalyst / Radeon Software Linux driver stack until that time.
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."
Canonical's Timo Aaltonen also confirmed support isn't coming until AMD rolls out their new Linux driver architecture later in the year. "Can't be done, sorry. AMD won't support fglrx on 16.04*, period. There will be a userspace blob released later this year that should cover the missing bits and it will be added to 16.04, but it's been well known for quite a while already that they were moving towards a shared core stack (amdgpu kernel driver), and we had to make a decision for 16.04. And installing the package from AMD doesn't help, as it doesn't support the xserver 1.18 video ABI, which got in xenial earlier this week and is what removed the incompatible driver from your system."
At least when this new driver stack does arrive, we won't need to worry so often about Linux kernel or xorg-server video ABI breakage since the AMDGPU kernel driver is open-source and mainlined while the DDX component is the open-source xf86-video-amdgpu. As far as when this driver stack will be out, it's "later this year", while in my past communications with various AMD/RTG representatives in the past few months has sounded like "middle of the year" / "summer". I'd guess around the time that AMD's next-generation hardware (Polaris) is announced since the company isn't bringing up any new hardware on their current driver stack. Polaris sounds like it's still on track for an announcement in June around Computex.