Попробуйте это первым:
sudo apt-get install --reinstall apt
Я попробовал это сам, никакого риска для вашей системы.
Если это не сработает, вам придется получить пакет от http://packages.ubuntu.com/.
Выберите подходящий для распространения. И установите его с помощью dpkg:
sudo dpkg -i apt_#version#.deb
Все должно работать нормально, но я не тестировал это.