Comment 6 for bug 1299378

Indeed ssh has a misfeature of applying the local locale to the remote session even though the remote server doesn't have that locale available. That breaks a lot of things, but it breaks postgresql particularly hard. This was fixed around raring in this version:

postgresql-common (145) unstable; urgency=low
[...]
  * debian/maintscripts-functions, configure_cluster(): Do not trust the
    locale from the environment, as programs like ssh and sudo propagate
    remote and user locale by default. Instead, only use the locale settings
    from /etc/environment and /etc/default/locale, to prevent trying to
    configure the default cluster with a nonexisting or hard to predict
    locale. (LP: #969462, also see Debian #700271)

 -- Christoph Berg <email address hidden> Mon, 10 Jun 2013 17:01:01 +0200

Hence this is really a duplicate of bug 969462, I'm updating the status of this.