Acabei de encontrar uma solução para este problema! Aqui está ..
1- Pare e solte seu cluster atual:
$ sudo pg_dropcluster --stop 9.3 main
2- Crie um novo cluster com a localidade correta:
$ sudo locale-gen pt_BR.UTF-8
$ sudo pg_createcluster --locale pt_BR.UTF-8 9.3 main
3- Confirme se funcionou como esperado:
$ sudo -u postgres psql
(9.3)
=> show LC_COLLATE;