Eu tive o mesmo problema e depois de bater minha cabeça contra o tempo suficiente percebi que eu tinha um pgdg.list obsoleto em minhas fontes. Depois de remover e adicionar novamente, tudo é ótimo.
sudo rm /etc/apt/sources.list.d/pgdg.*
echo "deb http://apt.postgresql.org/pub/repos/apt/ xenial-pgdg main" | sudo tee /etc/apt/sources.list.d/pgdg.list
wget --quiet -O - https://www.postgresql.org/media/keys/ACCC4CF8.asc | sudo apt-key add -
sudo apt-get update -y
sudo apt-get install pgadmin3