Я, помнится, когда столкнулся с таким же под W2K, просто при создании нового соединения поставил галочку на пунктик (не помню, как звучит точно) "Использовать правила набора" (перед этим вводятся правила вручную - код города, итд.) или что-то в этом роде: и сразу все заработало, как надо. Я перед этим пользовал Win98 - так этому удивился