Issue or Bug. The shading of an object changes when deselected in "Smooth" mode. (Why Radeon Users May Want to Avoid Ubuntu 16.04)
If Blender 3D is running fine on your Linux distro and your considering about upgrading to the latest Linux distro (in my situation to Ubuntu 16.04). 

First check if they have released new drivers or if there even are drivers that support your upgrade. 

Especially for AMD/ATI/Readon Graphic cards, you may want to stick to your current OS version.

They have stopped working on new drivers for AMD Ubuntu 16.04, 

Link: http://www.omgubuntu.co.uk/2016/03/ubuntu-drops-amd-catalyst-fglrx-driver-16-04

Also useful

Link: https://askubuntu.com/questions/744050/im-using-ubuntu-16-04-and-theres-no-fglrx

Link: https://wiki.ubuntu.com/XenialXerus/ReleaseNotes#fglrx

UPDATE 31-05-2016

Some interesting new developments: AMD's gaming-optimized AMDGPU-PRO driver for Linux is in beta.

Link: http://www.pcworld.com/article/3075837/linux/amds-gaming-optimized-amdgpu-pro-driver-for-linux-is-in-beta.html

Still in Beta and won't support GPUs older/lower than the Radeon HD 7000 series.

Ubuntu still recommends sticking with Ubuntu 14.04.