Faça o download do instalador do site da AMD (a partir deste post, a versão estável mais recente é 13.1, que não acredito estar disponível no PPA neste momento), execute o instalador (você precisará de cabeçalhos de kernel, gcc, e algumas outras coisas, basta olhar para o log quando o instalador falhar). Certifique-se de criar debs do Ubuntu a partir do instalador ao invés de instalar diretamente do script amd. Existem algumas dependências que o instalador não lhe informará a menos que você crie debs. Sem eles, não funcionará com dpms (o seu display será desligado para economizar energia) e você vai querer jogar o seu computador pela janela (foi lá).
Estou executando o fglrx 13.1 agora mesmo sem problemas (além do uso de 100% da CPU quando a tela é desligada (é um bug que será consertado em breve, mas você pode contornar isso configurando a opção vsync no catalisador). controle para "on, a menos que a aplicação especifique o contrário")).
Bug do Launchpad para 100% de uso da CPU no modo de espera do dpms.
A solução # 1 funciona para mim.