Ok, então descobri o problema.
Essencialmente, eu estava instalando uma versão antiga do apt (como o idiota que eu sou). Basicamente, eu tinha o arquivo de biblioteca apt libapt-pkg5.0 . Este arquivo de biblioteca corresponde ao arquivo .deb encontrado aqui . Depois de baixar esse arquivo (com wget ou seu navegador), você poderá instalá-lo com dpkg -i apt_1.2.15ubuntu0.2_amd64.deb . Uma vez que isso aconteça, tudo bem para você ir.
Obrigado às pessoas que tentaram me ajudar.