Du sollst schlicht und ergreifend einen neueren Kernel und X Treiber testen, das geht nicht wenn du auf einen Treiber beharrst der damit nicht kompatibel ist - früher oder später musst du ohnehin wechseln. Es geht nebenbei auch ganz ohne Grafiktreiber...
So, nach einer Weile habe ich nun einen anderen Treiber zum laufen bekommen (AMDGPU-PRO 16.60) unter Ubuntu 16.04.1 und das Problems scheint behoben zu sein! Viele Dank für die Hilfe!