Eu tenho exatamente o mesmo problema. Eu tenho dois monitores, um em DVI, um em VGA. Tudo funcionou bem com o Kubuntu 15.10.
Agora, com o 16.04, você pode ver que durante a inicialização, o monitor VGA permanece preto, mas o Ubuntu acha que ele foi ativado. Também para mim, a única solução é desativar a segunda tela nas configurações do sistema e reativá-la. Então, em 99% dos casos, funciona.
Eu tenho uma placa gráfica onboard AMD / ATI, e parece que esta é a fonte do nosso problema, veja aqui: link
(alemão) link
Portanto, só podemos esperar que os drivers de código aberto melhorem em breve .....: - /