The following bug has been logged online:

Bug reference: 2692
Logged by: Sergiy Vyshnevetskiy
Email address: serg (AT) vostok (DOT) net
PostgreSQL version: 8.1.4
Operating system: FreeBSD-6 stable
Description: psql sends natively-localized strings to database
without setting client_encoding first
Details:

psql mixes natively-localized string in SQL commands without setting
client_encoding first. Looks like we _really_ need some code in configure
script to find acceptable native names for our database charsets.

%zsh 1 11:27 serg@serg p0 /home/serg
set | egrep -a '^LANG|^LC_|^MM_CHAR'
LANG=ru_RU.KOI8-R
MM_CHARSET=KOI8-R
%zsh 0 11:27 serg@serg p0 /home/serg
psql -l
ERROR: invalid byte sequence for encoding "UTF8": 0xe9cdd1
%zsh 1 11:27 serg@serg p0 /home/serg
psql -d postgres
SET
Welcome to psql 8.1.4, 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

#psql = serg@[local]:5432 postgres
\encoding KOI8
#psql = serg@[local]:5432 postgres
\l
Список баз данных
Имя | Владелец | Кодировка
------------+----------+-----------
postgres | pgsql | UTF8
template0 | pgsql | UTF8
template1 | pgsql | UTF8
(записей: 3)

#psql = serg@[local]:5432 postgres

---------------------------(end of broadcast)---------------------------
TIP 3: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

"Sergiy Vyshnevetskiy" <serg (AT) vostok (DOT) net> writes:
Actually, psql has no business sending those strings to the server at
all --- it's just laziness in describe.c not to find another method of
attaching the headings to the output tables ...

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 6: explain analyze is your friend