Eu tive o mesmo problema com a minha Radeon HD 7750, atualizando a partir de 12.10 64 bits e tentando iniciar o Ubuntu Gnome 13.04 a partir de um pendrive.
A solução foi bem simples: instalar o fglrx-updates.
Vá para as configurações do sistema (ou similar, meu Ubuntu está em Português), clique no ícone de software e atualizações, vá para a guia de drivers adicionais e escolha fglrx-updates.
Eu joguei Anomaly 2 beta hoje perfeitamente bem. :)