Problem with locales on Linux with 9.3.4

Hi,
I'm running Pg 9.3.4 on Ubuntu Linux 12.04/Precise. Pg is installed from
PGDG repo (http://apt.postgresql.org/pub/repos/apt/)

It somehow got database created in locale that it can't now open:

$ psql
psql: FATAL: database locale is incompatible with operating system
DETAIL: The database was initialized with LC_COLLATE "en_GB.UTF-8", which
is not recognized by setlocale().
HINT: Recreate the database with another locale or install the missing
locale.

When I connect to another database, I can see that:

List of databases
Name | Owner | Encoding | Collate | Ctype
| Access privileges
-----------------+----------------+----------+-------------+-------------+-----------------------
xxxxxxxxxxxxxxx | xxxxxxxxxxxxxx | UTF8 | pl_PL.UTF-8 | pl_PL.UTF-8 |
postgres | postgres | UTF8 | en_GB.UTF-8 | en_GB.UTF-8 |
template0 | postgres | UTF8 | en_GB.UTF-8 | en_GB.UTF-8 |
=c/postgres +
| | | | |
postgres=CTc/postgres
template1 | postgres | UTF8 | en_GB.UTF-8 | en_GB.UTF-8 |
=c/postgres +
| | | | |
postgres=CTc/postgres
(4 rows)

Locale settings in Pg:

# select name, setting from pg_settings where name ~ '^lc_';
name | setting
-------------+-------------
lc_collate | pl_PL.UTF-8
lc_ctype | pl_PL.UTF-8
lc_messages | en_US.UTF-8
lc_monetary | en_US.UTF-8
lc_numeric | en_US.UTF-8
lc_time | en_US.UTF-8
(6 rows)

The thing is that system knows about en_GB:

$ locale -a
C
cs_CZ.utf8
C.UTF-8
de_DE.utf8
en_GB
en_GB.iso88591
en_GB.iso885915
en_GB.utf8
en_US.utf8
pl_PL.utf8
POSIX
sk_SK.utf8

$ LC_ALL=en_GB.UTF-8 locale
LANG=en_GB.UTF-8
LANGUAGE=
LC_CTYPE="en_GB.UTF-8"
LC_NUMERIC="en_GB.UTF-8"
LC_TIME="en_GB.UTF-8"
LC_COLLATE="en_GB.UTF-8"
LC_MONETARY="en_GB.UTF-8"
LC_MESSAGES="en_GB.UTF-8"
LC_PAPER="en_GB.UTF-8"
LC_NAME="en_GB.UTF-8"
LC_ADDRESS="en_GB.UTF-8"
LC_TELEPHONE="en_GB.UTF-8"
LC_MEASUREMENT="en_GB.UTF-8"
LC_IDENTIFICATION="en_GB.UTF-8"
LC_ALL=en_GB.UTF-8

I straced Pg, and it showed:

17:18:42.386260 open("/usr/lib/locale/en_GB.UTF-8/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000014>
17:18:42.386299 open("/usr/lib/locale/en_GB.utf8/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000014>
17:18:42.386337 open("/usr/lib/locale/en_GB/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000014>
17:18:42.386374 open("/usr/lib/locale/en.UTF-8/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000016>
17:18:42.386418 open("/usr/lib/locale/en.utf8/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000014>
17:18:42.386455 open("/usr/lib/locale/en/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000015>
17:18:42.386492
open("/usr/share/locale-langpack/en_GB.UTF-8/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000015>
17:18:42.386530
open("/usr/share/locale-langpack/en_GB.utf8/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000013>
17:18:42.386562 open("/usr/share/locale-langpack/en_GB/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000011>
17:18:42.386591 open("/usr/share/locale-langpack/en.UTF-8/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000008>
17:18:42.386618 open("/usr/share/locale-langpack/en.utf8/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000009>
17:18:42.386645 open("/usr/share/locale-langpack/en/LC_COLLATE",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory) <0.000008>
17:18:42.386723 write(2, "2014-06-06 15:18:42 GMT FATAL: database
locale is incompatible with operating system\n2014-06-06 15:18:42 GMT
DETAIL: The database was initialized with LC_COLLATE \"en_GB.UTF-8\",
which is not recognized by setlocale().\n2014-06-06 15:18:42 GMT
HINT: Recre"..., 324) = 324 <0.000023>

In /usr/lib/locale, I have only:
1. Directory C.UTF-8
2. File: locale-archive

It looks like if system locale was "packed" into this archive, but Pg for
some reason cannot open it, and required locale files to be separately in
subdirectories.

Is it possible? Anyone encountered something like this before? If so - what
can be done? I didn't found any way to "unpack" the archive with locales.

depesz