Eu tenho esse mesmo problema ao tentar instalar fglrx ou fglrx-updates no meu HP dv6-6117 apenas no outro dia. Acabei conseguindo instalar pela primeira vez:
sudo apt-get install --install-recommends xserver-xorg libgl1-mesa-glx libeg1-mesa-drivers
Apenas uma palavra de aviso, meu touchpad foi temporariamente desativado depois de fazer isso e instalar o fglrx, mas ele conseguiu instalar o fglrx.