Which kernel are you using? Check this with uname -r. I am not a fan of the AMD proprietary drivers on Linux. I find lots of issues with them. I prefer running the open source drivers and newer kernels have many new fixes and features for AMD graphics. You can take the OPEN SOURCE ROUTE, or the PROPRIETARY ROUTE.
OPEN SOURCE ROUTE
If you are using 3.13, then try the newer 3.16 kernel
sudo apt-get install --install-recommends linux-generic-lts-utopic
or try the entire Utopic LTS Enablement Stack which is better...
sudo apt-get install --install-recommends linux-generic-lts-utopic xserver-xorg-lts-utopic libgl1-mesa-glx-lts-utopic libegl1-mesa-drivers-lts-utopic
If you are already running 3.16, then try removing the Utopic LTS Enablement Stack
sudo apt-get remove linux-generic-lts-utopic xserver-xorg-lts-utopic libgl1-mesa-glx-lts-utopic libegl1-mesa-drivers-lts-utopic
If none of this helps, you can try the newest stable kernel. This is a bit more tricky, and could cause some issues, but I have been running the linux 4.0 kernel on Ubuntu 14.04 for a while now with no issues.
mkdir linux4-0-4
cd linux4-0-4
wget http://kernel.ubuntu.com/~kernel-ppa/mainline/v4.0.4-wily/linux-headers-4.0.4-040004-generic_4.0.4-040004.201505171336_amd64.deb http://kernel.ubuntu.com/~kernel-ppa/mainline/v4.0.4-wily/linux-image-4.0.4-040004-generic_4.0.4-040004.201505171336_amd64.deb http://kernel.ubuntu.com/~kernel-ppa/mainline/v4.0.4-wily/linux-headers-4.0.4-040004_4.0.4-040004.201505171336_all.deb
sudo dpkg -i linux-headers-4.0*.deb linux-image-4.0*.deb
After installing or removing any kernels, you will need to reboot in order to test them.
PROPRIETARY ROUTE
You can install the AMD proprietary Catalyst driver fairly easily in Ubuntu 14.04. Simply run
sudo apt-get install fglrx
sudo apt-get install fglrx xvba-va-driver libva-glx1 libva-egl1 vainfo
sudo amdconfig --initial
If you are using multiple AMD graphics cards or AMD dual graphics (i.e.: notebook users), use:
sudo amdconfig --adapter=all --initial
After installing or removing Catalyst, you will need to reboot in order to test.