Verifique a autenticidade / validade do seu download
md5sum amd-catalyst-13.12-linux-x86.x86_64.zip
2418a94b699fe8fdec01ccd32f684c90 amd-catalyst-13.12-linux-x86.x86_64.zip
Se a sua soma não corresponder, você precisará baixar novamente o driver (que é o que eu suspeito).
Faça o download do seu driver
wget --referer='http://support.amd.com/en-us/download/desktop?os=Linux+x86' http://www2.ati.com/drivers/linux/amd-catalyst-13.12-linux-x86.x86_64.zip
Descompacte o driver
unzip amd-catalyst-13.12-linux-x86.x86_64.zip
Instalar driver
sudo bash amd-catalyst-13.12-linux-x86.x86_64.run