По непонятной причине сегодня вечером gaim отказался коннектиться совсем, было такое чувство что он даже не пытается соединиться с сервером. "Ошибка соединения с сервером". Не помогло ни использование прокси, ни смена icq-серверов.. Зато появился стимул перейти на pidgin.
sudo apt-get remove gaim
Скачал отсюда deb-пакеты pidgin-data и pidgin , попробовал поставить - вылезла упущенная зависимость libsilc, решилось банальным sudo apt-get install libsilc.
Pidgin коннектится хорошо, интерфейс приятнее чем у gaim.