The following bug has been logged online:

Bug reference: 2293
Logged by: Sergey Rosenfeld
Email address: serg (AT) ung (DOT) ru
PostgreSQL version: 8.1.3
Operating system: Debian GNU/Linux (sid)
Description: primary key and cyrillic
Details:

postgres:~$ /usr/lib/postgresql/8.1/bin/pg_controldata
/var/lib/postgresql/8.1/main
<...skipped cyrillic koi8-r output ...>
LC_COLLATE: ru_RU.koi8r
LC_CTYPE: ru_RU.koi8r

postmaster works in same locale environment

postgres:~$ psql
Welcome to psql 8.1.3, the PostgreSQL interactive terminal.

Type: \copyright for distribution terms
\h for help with SQL commands
\? for help with psql commands
\g or terminate with semicolon to execute query
\q to quit

postgres=# select version();
version
----------------------------------------------------------------------------
----------------------------------
PostgreSQL 8.1.3 on i486-pc-linux-gnu, compiled by GCC cc (GCC) 4.0.3
20060212 (prerelease) (Debian 4.0.2-9)
(1 запись)

postgres=# show server_encoding;
server_encoding
-----------------
KOI8
(1 запись)

postgres=# show client_encoding;
client_encoding
-----------------
KOI8
(1 запись)
postgres=# create table test( s varchar(20) primary key );
NOTICE: CREATE TABLE / PRIMARY KEY создаст
подразумеваемый индекс "test_pkey" для
таблицы "test"
CREATE TABLE
postgres=# \d test
Таблица "public.test"
Колонка | Тип | Модификаторы
---------+-----------------------+--------------
s | character varying(20) | not null
Индексы:
"test_pkey" PRIMARY KEY, btree (s)

postgres=# insert into test values( 'фыва фыва' );
INSERT 0 1
postgres=# insert into test values( 'фыва фыва' );
INSERT 0 1
postgres=# select * from test;
s
-----------
фыва фыва
фыва фыва
(записей: 2)

What about PRIMARY KEY? If i use ascii symbols, all works fine:

postgres=# insert into test values( 'asdf asdf' );
INSERT 0 1
postgres=# insert into test values( 'asdf asdf' );
ERROR: повторный ключ нарушает констрейнт
UNIQUE "test_pkey"

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match