Ubuntu 16.04 does ship with a pretty old version of Mesa (full major version behind, about to be 2 major verions as Mesa 13 is in the RC stage) which probably isn't helping matters. Unfortunately, while there are some PPAs that make it fairly easy to install a bleeding edge build, there's not really a convenient way to install the latest stable release.
For some context, the reason fglrx/Catalyst has not been updated is due to an in progress driver transition for AMD cards on Linux. Generally speaking, Linux video drivers are split into a kernel part and a user space part. For quite some time, AMD has maintained two completely separate driver stacks on Linux. For the user space side, this didn't represent a huge amount of duplication of effort as most of the code is shared with the OpenGL portion of their Windows driver, but for the kernel side it was a bunch of wasted effort. A while back, they started on a new open source kernel driver, called amdgpu, that could provide the necessary facilities for both their open source and proprietary driver efforts. The new proprietary driver (AMDGPU-Pro) targets this kernel module. Unfortunately, amdgpu does not have production-ready support for GCN 1.0 GPUs like the 8570. This will get fixed eventually, but that doesn't really help you now.
[1] https://support.amd.com/en-us/kb-articles/Pages/AMD-Radeon-G...
Then Ubuntu 16.04 comes out, and guess what? No fglrx driver support any more [2] and users report the open source drivers use about a core and a half worth of CPU, slowing down their entire machines. Apparently our only options are to buy new cards or stay on 14.04 indefinitely.
Meanwhile, I had an nVidia card and I was able to upgrade to 16.04 with no problems at all.
This week you might have resolved not to buy from nVidia - but in the same week I've resolved not to buy from ATI.
[1] https://certification.ubuntu.com/hardware/201302-12679/ [2] http://www.omgubuntu.co.uk/2016/03/ubuntu-drops-amd-catalyst...