A primeira coisa que eu faço é instalar as versões mais novas do FGLRX, já que você tem a versão disponível no lançamento da distro. você não precisa obter uma versão da AMD, neste momento, você pode obter a versão de atualizações do repositório.
Primeiro, desinstale sua versão atual.
sudo apt-get purge fglrx fglrx-amdcccle
Em seguida, instale a versão mais recente, disponível no repositório
sudo apt-get install fglrx-updates fglrx-amdcccle-updates
Reinicie o computador, faça o login novamente em sua área de trabalho e informe seus resultados de FPS novamente.
Também quero mencionar que você obterá taxas de quadros muito baixas se tiver a opção "Aguardar atualização vertical" configurada para qualquer uma das opções "LIGADAS". Certifique-se de que esteja definido como "Off, a menos que o aplicativo especifique". Você pode encontrá-lo no Catalyst Control Center. Esse é o único outro motivo, que eu poderia pensar, que causaria FPS tão baixo em uma configuração correta. Estou 100% sério, você precisa verificar essa configuração. Esta não é uma mera sugestão, é tão significativa para as pontuações do FPS.