Estou na situação de sorte para responder à minha própria pergunta:
Embora os sintomas descritos na pergunta postada por Zacharee1 sejam diferentes, tentei instalar os dois drivers do Oibaf (não mudei nada - ainda mostrei "radeon" após a reinicialização e ainda tinha os mesmos problemas) e amdgpu_pro (não renderizaria nada mas o fundo da área de trabalho - eu tive que desinstalá-lo usando um shell de texto).
O que resolveu o problema para mim no final foi atualizar o kernel:
mkdir tmp && cd tmp
wget http://kernel.ubuntu.com/~kernel-ppa/mainline/v4.6-yakkety/linux-image-4.6.0-040600-generic_4.6.0-040600.201606100558_amd64.deb
wget http://kernel.ubuntu.com/~kernel-ppa/mainline/v4.6-yakkety/linux-headers-4.6.0-040600-generic_4.6.0-040600.201606100558_amd64.deb
wget http://kernel.ubuntu.com/~kernel-ppa/mainline/v4.6-yakkety/linux-headers-4.6.0-040600_4.6.0-040600.201606100558_all.deb
sudo dpkg -i *.deb
E reiniciado (usando opções avançadas e escolhendo o kernel 4.6, já que a entrada padrão do grub não foi atualizada). Não há mais problemas. Eu instalei e executei glmark2
e obtive 11872 pontos, com 890 FPS no teste mais lento (e alguns acima de 15k FPS), então acho que isso significa que meus drivers gráficos estão funcionando. Eles ainda aparecem como radeon
btw.
No entanto, eu vi o Chrome tendo problemas de renderização estranhos, mas eu poderia corrigi-lo desabilitando a aceleração de hardware nas configurações. Vou monitorar se algum outro programa tem esses problemas e relato aqui se encontrar uma solução melhor para o Chrome.