Eu tive o mesmo problema que você. Eu fiz EXATAMENTE o que você fez e terminei com os mesmos resultados: upgrade falhou! Quando você muda a versão do Ubuntu, você faz uma atualização. Um upgrade de distribuição (Ubuntu). Quando você altera apenas uma versão de software, você faz uma atualização.
Após três dias de tentativas, desisti e baixei uma imagem ISO e a instalei via liveUSB.
De qualquer forma, você deve estar ciente de que uma atualização é possível via LiveUSB e é mais rápida que a atualização do comando Terminal. A transferência de arquivos via USB é mais rápida e muito mais confiável do que uma conexão com a Internet. Eu pessoalmente prefiro fazer uma instalação completamente nova com cada versão do Ubuntu, porque eu não herdo todo o lixo do anterior e eu não estrago a lista de fontes com o ppas errado. Na verdade, é muito simples: inicialize o LiveUSB, entre na área de trabalho, clique no ícone Instalar o Ubuntu e escolha a opção "Substituir o Ubuntu 14 pelo Ubuntu 16".