Comment 35 for bug 1276379

Confirmed with:
# lspci | grep -i vga
02:00.0 VGA compatible controller: Advanced Micro Devices, Inc. [AMD/ATI] RV730/M96 [Mobility Radeon HD 4650/5165]
# lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 12.04.4 LTS
Release: 12.04
Codename: precise
#uname -a
Linux dell-studio-1747 3.2.0-60-generic #91-Ubuntu SMP Wed Feb 19 03:54:44 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux

To solve the problem, we have to:
- download manually the proposed driver by amd official website on http://support.amd.com/fr-fr/download/
(in my case, the proposed driver is: amd-driver-installer-catalyst-13.1-legacy-linux-x86.x86_64.run)
- extract and run:
    amd-driver-installer-catalyst-13.1-legacy-linux-x86.x86_64.run --listpkg # and find <your_distrib_tag> in the list
    sudo amd-driver-installer-catalyst-13.1-legacy-linux-x86.x86_64.run --buildandinstallpkg <your_ditrib_tag>
- fix apt marks
    # Because this is the higher driver version we can expect for a 4xxx series
    sudo apt-mark hold fglrx
    sudo apt-mark hold fglrx-amdcccle

The proposed driver by amd is 8.970 and it works like a charm.