Ubuntu – Pre-requisites for AMD Graphics Drivers

sudo apt-get remove fglrx 

then for newest ati driver:

wget http://www2.ati.com/drivers/linux/ati-driver-installer-11-4-x86.x86_64.run

If you have a 64 bit system, then install this before anything:

sudo apt-get install ia32-libs

Once dowloaded right-click the .run file and set it to run as executable.

then.

cd /path_of_the_file       

This is for 32 bit only:

sudo sh ./ati-driver-installer-11-4-x86.x86_64.run

This is for 64 bit only:

sudo sh ./ati-driver-installer-11-4-x86.x86_64.run --buildpkg Ubuntu/natty

sudo dpkg -i fglrx*.deb

Once it's done.

  sudo aticonfig --initial -f

that's all you have to do.

Alternatively you can add this ppa.

   sudo add-apt-repository ppa:ubuntu-x-swat/x-updates
   sudo apt-get update
   sudo apt-get install fglrx

from the error it seems that you need to install the kernels headers. You can do that by installing the linux-headers-generic package.

(In terminal) sudo apt-get install linux-headers-generic

However, did you tried installing the proprietary drivers directly from ubuntu instead from the Amd website. For that (I suggest to do that since it would be automatically updated and easier) install the package fglrx (or if you want a more recent version use fglrx-updates).

sudo apt-get install fglrx