Tendo o mesmo problema com um novo 16.04 que eu reinstalei porque tendo esse problema com um anterior 14.04 LTS e depois de anos trabalhando bem, um dia ... começou a produzir como a imagem. Depois do Google, consegui recuperá-lo. Espero que ajude a qualquer um.
Primeiro, criamos um novo modo de monitor (esses dados são extraídos da cvt 1920 1080 60, basta copiar o que acontece depois do nome da modeline):
xrandr --newmode 1920x1080T 173.00 1920 2048 2248 2576 1080 1083 1088 1120 -HSync +VSync
Agora este novo modo de tela criado (1920x1080T) vamos adicioná-lo às capacidades do monitor, no meu caso a saída HDMI1 (você pode ver os nomes das saídas possíveis digitando apenas o comando xrandr):
xrandr --addmode HDMI1 1920x1080T
se você digitar novamente xrandr, ele aparecerá na lista do HDMI1.
Agora você deve usar este novo modo para corrigir o problema:
xrandr --output HDMI1 --mode 1920x1080T
Isso é tudo! Espero que ajude!