Ну что же, сам спросил, сам и отвечаю.

Все дело в переводе из Unicode16 в ASCII. После того как логин и пароль к прокси-серверу были введены FireFox перевод их в Unicode (он называет его UTF16). А перед отправлением на прокси-сервер переводит обратно в ASCII, но не верно!!! Он просто берет младшую часть Unicode! Для английских букв это не важно их Unicode имеет 0 в старшей части, а вот русские буквы превращаются в какую-то ерунду.

Пример преобразования букв ASCII->Unicode->ASCII

Char    ASCII        Unicode          ASCII
А     0xC0        0x0410           0x10
Б     0xC1        0x0411           0x11
В     0xC2        0x0412           0x12

A     0x41        0x0041           0x41
B     0x42        0x0042           0x42
C     0x43        0x0043           0x43

Для знатоков скажу, что это происходит в mozilla\netwerk\protocol\http\src\nsHttpBasicAuth.cpp

Функция называется nsHttpBasicAuth::GenerateCredentials

    // we work with ASCII around here
    nsCAutoString userpass;
   

LossyCopyUTF16toASCII

(user, userpass);
    userpass.Append(':'); // always send a ':' (see bug 129565)
    if (password)
       

LossyAppendUTF16toASCII

(password, userpass);

    // plbase64.h provides this worst-case output buffer size calculation.
    // use calloc, since PL_Base64Encode does not null terminate.
    *creds = (char *) calloc(6 + ((userpass.Length() + 2)/3)*4 + 1, 1);
    if (!*creds)
        return NS_ERROR_OUT_OF_MEMORY;

    memcpy(*creds, "Basic ", 6);
    PL_Base64Encode(userpass.get(), userpass.Length(), *creds + 6);

Как очевидно из названия функция преобразует с потерями.

Ну вот, ошибка найдена. Как мне теперь сообщить об этом разработчикам? Если учесть, что английский я очень плохо знаю, еле-еле читать получается.