Fixed by installing the 'Experimental Beta' proprietary drivers from AMD via the 'Additional Drivers' in the settings panel.
The very drivers most the guides say NOT to use?