eu também estava tendo quase o mesmo problema com o Ubuntu 13.04 eu instalei a extensão do shell do gnome "Radeon Power Profile Manager", que tem a opção de colocar o perfil no modo baixo que reduz um pouco a temperatura, mas isso é para o gnome shell apenas com drivers de código aberto
link para a extensão: link