А бери версию 7.1 и собирай с --enable-local,
Запускать postmaster автор локали рекомендует скриптом -
#!/bin/sh
export LC_CTYPE=koi8-r
export LC_COLLATE=koi8-r
postmaster -B 1024 -S -D/usr/local/pgsql/data/ -o '-Fe'
Но что любопытно, в RH 7.2 и FreeBSD 4.4 все работает "из коробки", так что возможно дело именно в версии