Encontrei o mesmo problema usando o recurso "Sobre este computador" > Rota 'Upgrade' em um sistema 14.04 LTS totalmente atualizado. Eu tenho software de vários repositórios alternativos, que vários posts sugerem que podem ter causado o problema.
grep Broken /var/log/dist-upgrade/apt.log
relataram 163 linhas, muitas das quais relacionadas ao gnuplot. Eu observei algumas outras postagens que relataram o gnuplot como um problema.
Eu apaguei os dois pacotes do gnuplot instalados no meu sistema usando o Synaptic e então fechei o Synaptic. Curiosamente, ao filtrar com 'instalado (atualizável)' no Synaptic, apenas estes dois pacotes apareceram (gnuplot e gnuplotX11) e ambos tinham um ponto de exclamação na caixa de seleção.
Então do-release-upgrade
funcionou.