Цитата от Rap-Radio.ru :
Тебе нужно использовать русский ICQ-Cервер(@jabber.ru, @rambler.ru), вместо стандартного.
Мобильники проживающие на территории России не любят стандартный, америкосовский ICQ-Cервер (login.icq.com)

P.S. Иногда у мобильный провайдеров глючит DNS-Сервер, так что можешь попробовать вместо доменного имени сервера - вписывать ip-адрес сервера. Например, вместо login.icq.com - 64.12.161.153

Вот собственно и всё.