Se você estiver executando a versão do servidor do Ubuntu, você pode tentar executar
sudo apt-get update
para atualizar os pacotes disponíveis e, em seguida, tentar novamente a instalação com
sudo apt-get install postgresql
Se você estiver executando a versão desktop do Ubuntu, no entanto, eu sugiro instalar o postgresql através do Ubuntu Software Center, já que isso sempre funcionou melhor para mim.