Respondendo a minha própria pergunta. Isso é meio irritante, a primeira pergunta em qualquer site do StackExchange não funciona bem para mim.
Eu já tinha feito isso, mas de alguma forma trabalhei desta vez. Fez isso:
- sudo apt-get update & & sudo apt-get upgrade
- sudo apt-get purgar postgresql *
- sudo apt-get -f instalar
- sudo apt-get instala postgresql
Funciona como um encanto.
Nota: adicionar o * no comando purge irá limpar todos os pacotes que começam com postgresql