Este é um problema antigo, mas darei outra solução, pois tive um problema muito semelhante após um recente Ubuntu 14.04 LTS = > Atualização 16.04 LTS (e não queria voltar para o 14.04, embora eu gostasse dos recursos do fglrx e da velocidade). Os sintomas: após a atualização, a minha resolução com o monitor Acer 24 "ficou presa com o não-nativo, apenas 1600x1200 (ou 1440x900 dependendo da seqüência de alimentação ou algo assim) vs. 1920x1200 nativa. Além disso, xrandr estava reclamando sobre gama, não podia decodificar as informações do EDID, adicionar modelos manualmente também não funcionou.
A solução que finalmente funcionava era remover os pacotes de atualizações do fglrx (sugerido por outra solução ), ou seja,
sudo apt remove fglrx-updates fglrx-updates-core
Depois disso, reinicie o driver radeon de código-fonte aberto e identifique corretamente o monitor e as duas saídas do cartão (DVI + HDMI) e, na verdade, a informação EDID fornecida pelo
xrandr --props | edid-decode
também mudou. Ainda houve alguns erros de meu monitor não cumprir com a norma EDID 1.3, mas, por exemplo, o nome do fabricante + data de compilação agora era exibido corretamente. E agora havia várias resoluções detectadas (1920x1200, 1600x1200, 1680x1050, etc.).