Em execução sudo apt-get install fglrx-dev fglrx-updates fglrx-updates-dev
Corrigido o problema. Por alguma razão, eu não consegui instalar todos os três de uma vez, então eu tive que instalar o fglrx-dev primeiro, e depois os outros dois estavam bem.
EDIT: Eu estava enganado, seguindo as instruções em este post funcionou perfeitamente.