Você tentou preencher o /etc/apt/sources.list? Este é o meu fie para 16.04 em aws:
$ cat /etc/apt/sources.list | grep -v '#'
deb link principal do xenial restrito deb-src link principal principal xenial
deb link atualizações xeniais principal restrito deb-src link xenial-updates main restrito
deb link universo xenial deb-src link xenial universo deb link universo xenial-updates deb-src link atualizações xeniais universo
deb link multiverso xenial deb-src link xenial multiverse deb link xenial-updates multiverse deb-src link atualizações xeniais multiverso
deb link xenial-backports universo restrito principal multiverse deb-src link xenial-backports main universo restrito multiverso
deb link xenial-security main restricted deb-src link xenial-security main deb restrito link xenial-security universo deb-src link xenial-security universo deb link xenial-security multiverse deb-src link xenial-security multiverso
executando
~ $ apt-cache madison libnet-ssleay-perl libauthen-pam-perl libio-pty-perl apt-show-versões python
mostra pacotes disponíveis a partir de repos selecionados
libnet-ssleay-perl | 1.72-1build1 | http://gb.archive.ubuntu.com/ubuntu xenial/main amd64 Packages libauthen-pam-perl | 0.16-3build2 | http://gb.archive.ubuntu.com/ubuntu xenial/universe amd64 Packages libio-pty-perl | 1:1.08-1.1build1 | http://gb.archive.ubuntu.com/ubuntu xenial/main amd64 Packages apt-show-versions | 0.22.7 | http://gb.archive.ubuntu.com/ubuntu xenial/universe amd64 Packages apt-show-versions | 0.22.7 | http://gb.archive.ubuntu.com/ubuntu xenial/universe i386 Packages python | 2.7.12-1~16.04 | http://gb.archive.ubuntu.com/ubuntu xenial-updates/main amd64 Packages python | 2.7.11-1 | http://gb.archive.ubuntu.com/ubuntu xenial/main amd64 Packages
Espero que isso ajude. Obrigado