Eu experimentei esse mesmo problema com essa atualização do postgresql.
A versão mais nova do postgres é 9.1.7, por algum motivo o 9.1.6 não está no repositório, então aqui está como eu fiz o downgrade para o 9.1.5:
sudo apt-get -V install postgresql-client-9.1=9.1.5-0ubuntu12.04
sudo apt-get -V install postgresql-9.1=9.1.5-0ubuntu12.04
Note que eu fiz o downgrade para o cliente primeiro. Parece que há um bug na atualização mais recente, que causa um erro de dependência entre o cliente e o servidor.
edite: Se você quiser evitar que o postgresql atualize no futuro, consulte esta página: link . Certifique-se de aplicar este método ao cliente e ao servidor.