Eu também tive esse mesmo revés. Essa abordagem foi a que usei e resolvi o problema do meu jeito:
Estamos removendo o apt de postgresql que era do repositório.
sudo apt-get remove -y --purge postgresql*
Em seguida, estamos fazendo uma lista de origens para baixar o Postgre diretamente da empresa.
sudo touch /etc/apt/sources.list.d/pgdg.list
sudo nano /etc/apt/sources.list.d/pgdg.list
e adicione esta linha ao pgdg.list
para 12.04 ou 12.10:
deb http://apt.postgresql.org/pub/repos/apt/ precise-pgdg main
para 13.04 ou 13.10
deb http://apt.postgresql.org/pub/repos/apt/ wheezy-pgdg main
Em seguida, pressione ctrl-x para salvar o pgdg.list e, finalmente, retorne à linha de comando.
Em seguida, pegamos as chaves para usar este pacote deb:
wget --quiet -O - https://www.postgresql.org/media/keys/ACCC4CF8.asc | \
sudo apt-key add -
sudo apt-get update
Em seguida, instalará o postgresql-9.3.