There are still issues with AMD/ATI Raedon graphics with Ubuntu 16.04 (whose libraries the Hardware Enablement kernel allows. See Below:
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:
As to how to recover from a Live USB, have you tried rolling back the upgraded libraries by purging the added files:
sudo apt-get purge linux-generic-lts-xenial xserver-xorg-core-lts-xenial xserver-xorg-lts-xenial xserver-xorg-video-all-lts-xenial xserver-xorg-input-all-lts-xenial libwayland-egl1-mesa-lts-xenial
Not sure if that would work to get you back to square one though, you may just have to reinstall. Hope you backed up your data! good luck.