On ubuntu 12.04, whenever I try to install a package using apt-get I'm greeted by:

The following packages have unmet dependencies:
 postgresql-9.1 : Depends: postgresql-client-9.1 but it is not going to be instal
led
E: Unmet dependencies. Try 'apt-get -f install' with no packages (or specify a so
lution).

apt-get install postgresql-client-9.1 generates:

The following packages have unmet dependencies:
 postgresql-client-9.1 : Breaks: postgresql-9.1 (< 9.1.6-0ubuntu12.04.1) but 9.1.3-2 is to be installed

apt-get -f install and apt-get remove postgresql-9.1 both give:

Removing postgresql-9.1 ...
 * Stopping PostgreSQL 9.1 database server
 * Error: /var/lib/postgresql/9.1/main is not accessible or does not exist
   ...fail!
invoke-rc.d: initscript postgresql, action "stop" failed.
dpkg: error processing postgresql-9.1 (--remove):
 subprocess installed pre-removal script returned error exit status 1
Errors were encountered while processing:
 postgresql-9.1
E: Sub-process /usr/bin/dpkg returned an error code (1)

So, apt-get is crippled, and I can't find a way out. Is there any way to resolve this without a re-install?

EDIT: apt-cache show postgresql-9.1 returns:

Package: postgresql-9.1
Priority: optional
Section: database
Installed-Size: 11164
Maintainer: Ubuntu Developers <[email protected]>
Original-Maintainer: Martin Pitt <[email protected]>
Architecture: amd64
Version: 9.1.6-0ubuntu12.04.1
Replaces: postgresql-contrib-9.1 (<< 9.1~beta1-3~), postgresql-plpython-9.1 (<< 9.1.6-0ubuntu12.04.1)
Depends: libc6 (>= 2.15), libcomerr2 (>= 1.01), libgssapi-krb5-2 (>= 1.8+dfsg), libkrb5-3 (>= 1.6.dfsg.2), libldap-2.4-2 (>= 2.4.7), libpam0g (>= 0.99.7.1), libpq5 (>= 9.1~), libssl1.0.0 (>= 1.0.0), libxml2 (>= 2.7.4), postgresql-client-9.1, postgresql-common (>= 115~), tzdata, ssl-cert, locales
Suggests: oidentd | ident-server, locales-all
Conflicts: postgresql (<< 7.5)
Breaks: postgresql-plpython-9.1 (<< 9.1.6-0ubuntu12.04.1)
Filename: pool/main/p/postgresql-9.1/postgresql-9.1_9.1.6-0ubuntu12.04.1_amd64.deb
Size: 4298270
MD5sum: 9ee2ab5f25f949121f736ad80d735d57
SHA1: 5eac1cca8d00c4aec4fb55c46fc2a013bc401642
SHA256: 4e6c24c251a01f1b6a340c96d24fdbb92b5e2f8a2f4a8b6b08a0df0fe4cf62ab
Description-en: object-relational SQL database, version 9.1 server
 PostgreSQL is a fully featured object-relational database management
 system.  It supports a large part of the SQL standard and is designed
 to be extensible by users in many aspects.  Some of the features are:
 ACID transactions, foreign keys, views, sequences, subqueries,
 triggers, user-defined types and functions, outer joins, multiversion
 concurrency control.  Graphical user interfaces and bindings for many
 programming languages are available as well.
 .
 This package provides the database server for PostgreSQL 9.1. Servers
 for other major release versions can be installed simultaneously and
 are coordinated by the postgresql-common package. A package providing
 ident-server is needed if you want to authenticate remote connections
 with identd.
Homepage: http://www.postgresql.org/
Description-md5: c487fe4e86f0eac09ed9847282436059
Bugs: https://bugs.launchpad.net/ubuntu/+filebug
Origin: Ubuntu
Supported: 5y
Task: postgresql-server

Package: postgresql-9.1
Priority: optional
Section: database
Installed-Size: 11164
Maintainer: Ubuntu Developers <[email protected]>
Original-Maintainer: Martin Pitt <[email protected]>
Architecture: amd64
Version: 9.1.5-0ubuntu12.04
Replaces: postgresql-contrib-9.1 (<< 9.1~beta1-3~), postgresql-plpython-9.1 (<< 9.1.5-0ubuntu12.04)
Depends: libc6 (>= 2.15), libcomerr2 (>= 1.01), libgssapi-krb5-2 (>= 1.8+dfsg), libkrb5-3 (>= 1.6.dfsg.2), libldap-2.4-2 (>= 2.4.7), libpam0g (>= 0.99.7.1), libpq5 (>= 9.1~), libssl1.0.0 (>= 1.0.0), libxml2 (>= 2.7.4), postgresql-client-9.1, postgresql-common (>= 115~), tzdata, ssl-cert, locales
Suggests: oidentd | ident-server, locales-all
Conflicts: postgresql (<< 7.5)
Breaks: postgresql-plpython-9.1 (<< 9.1.5-0ubuntu12.04)
Filename: pool/main/p/postgresql-9.1/postgresql-9.1_9.1.5-0ubuntu12.04_amd64.deb
Size: 4298028
MD5sum: 3797b030ca8558a67b58e62cc0a22646
SHA1: ad340a9693341621b82b7f91725fda781781c0fb
SHA256: 99aa892971976b85bcf6fb2e1bb8bf3e3fb860190679a225e7ceeb8f33f0e84b
Description-en: object-relational SQL database, version 9.1 server
 PostgreSQL is a fully featured object-relational database management
 system.  It supports a large part of the SQL standard and is designed
 to be extensible by users in many aspects.  Some of the features are:
 ACID transactions, foreign keys, views, sequences, subqueries,
 triggers, user-defined types and functions, outer joins, multiversion
 concurrency control.  Graphical user interfaces and bindings for many
 programming languages are available as well.
 .
 This package provides the database server for PostgreSQL 9.1. Servers
 for other major release versions can be installed simultaneously and
 are coordinated by the postgresql-common package. A package providing
 ident-server is needed if you want to authenticate remote connections
 with identd.
Homepage: http://www.postgresql.org/
Description-md5: c487fe4e86f0eac09ed9847282436059
Bugs: https://bugs.launchpad.net/ubuntu/+filebug
Origin: Ubuntu
Supported: 5y
Task: postgresql-server

Package: postgresql-9.1
Priority: optional
Section: database
Installed-Size: 11220
Maintainer: Martin Pitt <[email protected]>
Original-Maintainer: Martin Pitt <[email protected]>
Architecture: amd64
Version: 9.1.3-2
Replaces: postgresql-contrib-9.1 (<< 9.1~beta1-3~), postgresql-plpython-9.1 (<< 9.1.3-2)
Depends: libc6 (>= 2.15), libcomerr2 (>= 1.01), libgssapi-krb5-2 (>= 1.8+dfsg), libkrb5-3 (>= 1.6.dfsg.2), libldap-2.4-2 (>= 2.4.7), libpam0g (>= 0.99.7.1), libpq5 (>= 9.1~), libssl1.0.0 (>= 1.0.0), libxml2 (>= 2.7.4), postgresql-client-9.1, postgresql-common (>= 115~), tzdata, ssl-cert, locales
Suggests: oidentd | ident-server, locales-all
Conflicts: postgresql (<< 7.5)
Breaks: postgresql-plpython-9.1 (<< 9.1.3-2)
Filename: pool/main/p/postgresql-9.1/postgresql-9.1_9.1.3-2_amd64.deb
Size: 4284744
MD5sum: bad9aac349051fe86fd1c1f628797122
SHA1: a3f5d6583cc6e2372a077d7c2fc7adfcfa0d504d
SHA256: e885c32950f09db7498c90e12c4d1df0525038d6feb2f83e2e50f563fdde404a
Description-en: object-relational SQL database, version 9.1 server
 PostgreSQL is a fully featured object-relational database management
 system.  It supports a large part of the SQL standard and is designed
 to be extensible by users in many aspects.  Some of the features are:
 ACID transactions, foreign keys, views, sequences, subqueries,
 triggers, user-defined types and functions, outer joins, multiversion
 concurrency control.  Graphical user interfaces and bindings for many
 programming languages are available as well.
 .
 This package provides the database server for PostgreSQL 9.1. Servers
 for other major release versions can be installed simultaneously and
 are coordinated by the postgresql-common package. A package providing
 ident-server is needed if you want to authenticate remote connections
 with identd.
Homepage: http://www.postgresql.org/
Description-md5: c487fe4e86f0eac09ed9847282436059
Bugs: https://bugs.launchpad.net/ubuntu/+filebug
Origin: Ubuntu
Supported: 5y
Task: postgresql-server