kdepim-kmail-3.5.0-alt1: то же самое. 
Поэтому при ответе на такое письмо видим 
> ???????? 
вместо исходного текста. 
 

rpmquery -f /usr/bin/kmail
kdepim-kmail-3.5.6-alt3

Действительно, это потому что в:
в Настройка->Настроить Kmail...->Редактор писем->Кодировка
(Settings->Configure Kmail...->Редактор писем->Charset)
на первом месте стоит:us-ascii

Решение: поставить на первое место кодировку системную кодировку. Например: utf8
(locale).

В руководстве для этого пункта сказано:

Charset

Here you can manage the default charsets used for your own messages. Every
message you send will be checked if it is written in one of the listed charsets,
starting at the top of the list. If it is, this charset will be used. If it is
not, a dialog will show up and tell you that you manually have to choose a
charset using Options->Set Encoding.

If you select Keep original charset when replying or forwarding (if possible),
the original message's charset will be kept, unless there are now characters
that cannot be represented using that charset.

Как вариант, можно установить по умолчанию локальную кодировку для самой kmail.
Для этого _наверно_ нужно перекомпилировать пакет kmail заменив в:
~/RPM/kdepim/BUILD/kdepim-3.5.6/kmail

--- kmkernel.cpp-orig   2007-04-24 10:42:08 +0400
+++ kmkernel.cpp        2007-04-24 10:42:44 +0400
@@ -1492,7 +1492,7 @@
     KConfigGroupSaver saver(cfg, "Composer");
     if (cfg->readListEntry("pref-charsets").isEmpty())
     {
-      cfg->writeEntry("pref-charsets", "us-ascii,iso-8859-1,locale,utf-8");
+      cfg->writeEntry("pref-charsets", "locale,us-ascii,iso-8859-1,utf-8");
     }
   }
   readConfig();

Created attachment 1931 [details]
kmail: MultiPart message plain/text body encoding patch

Если письмо составлять в HTML тогда: kmail создает письмо из двух частей:
1-я часть : письмо в HTML
2-я часть : тоже самое письмо но в plain text

Вот вторая часть и не правильно составляется. А именно: кодирует не правильно
текст.

Вот патч который поправляет эту ошибку.

Отрепортил на багзиллу кде:
http://bugs.kde.org/show_bug.cgi?id=144779

*** Bug 8464 has been marked as a duplicate of this bug. ***

kdepim-kmail-3.5.6-alt4

Проверил, всё отлично.