Então, depois de uma boa noite de sono, decidi pesquisar no Google o problema com uma falha "sudo apt-get update" e descobri que o problema a seguir corrigiu meu problema:
ubuntu@tegra-ubuntu:~$ dpkg --print-foreign-architectures
i386
ubuntu@tegra-ubuntu:~$ sudo dpkg --remove-architecture i386
Aparentemente, eu adicionei uma arquitetura estrangeira "i386" e isso estava causando todos os problemas e não sei por que não vi isso antes.
Lá vai você, espero que isso ajude alguém.
Esse é o link que me ajudou a tentar essa abordagem. Não é exatamente o mesmo problema, mas a solução é a mesma: A atualização do apt-get falha no ubuntu 14.04