Зі схожим феноменом я стикався, коли пробував використовувати "готовопакований" gaim з RedHat8. З вирішенням цієї проблеми тоді я не перенапружувався, особливої потреби не було. Проте маю сказати, що 0.75 - це було давно. Остання версія 1.3.1. Коли ставив з вихідного коду 1.1.4, подібної проблеми взагалі не виникло. Тому дуже раджу перекомпілювати й апгрейднутись (можна спробувати й готовий поставити, пакети на gaim.sf.net). Від 0.75 до 1.3.1 changelog на півметра.
Якщо потрібно вказати кодування, що використовується в повідомленнях ICQ, натисніть (у випадку української локалі) "Сервіс"-"Облікові записи", виділіть ваш обліковий запис і натисніть "Змінити"-"Показати більше параметрів", і в графі "Кодування" вкажіть, наприклад, "cp1251" (з огляду на віндових співрозмовників:)). В 1.3.1 точно працює:)
