Давно, когда я ещё пользовался аськой под убунту, помнится, там был глюк как раз с добавлением новых пользователей и лечил я его удалением и новым запросом авторизации.
Если вы про icq, то я обычно новых пользователей добавлял через сайт аськи, там же авторизовывал, а потом в клиенте перелогинивался. Криво конечно, но я не так часто контакты добавлял.
