В Linux есть стандартный клиент. Он не только icq поддерживает но и другие меседжеры. Вроде IM называется, точно не помню. Если он у тебя еще не установлен, тогда заходишь в установку\удаление пакетов, смотришь программы для интрернета, ставишь галочку и устанавливаешь
На gaim подали в суд за плагиат, вот они и переименовались. Сам юзаю pidgin, но есть много проблем со стыковками с другими клиентами. Нравится sim, хотя многие предпочитают и стандартную kde`шную kopete, но я большой нелюбитель длинных зависимостей и не кдешник, а потому для поставленных рамок pidgin - самое то.