После долгих комментариев в сети, типа: Установите LC_MESSAGE и тому подобных, которые ни к чему не приводят.
Если LANG=ru_RU.KOI8-R - запуск должен выглядеть как
LC_ALL=$LANG licq
На самом деле видимо licq использует только одну, или несколько переменных из серии LC_ но выяснять не было ни времени ни желания.