Eu finalmente consegui resolver o problema. Daí postagem para a ajuda de outras pessoas que chegam a este post usando a pesquisa.
Nenhuma das técnicas mostradas acima funcionou para mim. Mas vá para o site da AMD (eu tenho o Radeon 7670 HD) e baixe o driver BETA do linux que vai resolver o seu problema.