Иногда юзаю под Киевстар ACE аську (либо Jimm, либо IM+) на Nokia E50.
Действительно, коннектится отвратительно почти всегда. Бывает, требуется несколько десятков или даже сотен попыток, пока соединится. За всё время лишь несколько раз коннект наступал моментально.

Так что если у кого не получается - дело лишь в терпении, пробуйте. Ну, и, понятное дело, зависит от того, как инженерный состав оператора настроил GPRS в конкретной местности.