Сегодня я сдался и поставил Mobile Partner на своей ubuntu 10.04. Не то, что бы она не соединялась вообще через стандартный Network Manager, но настолько плохо, что просто для того что бы связаться приходилось мучаться, дёргать модемом, перезагружаться (главное, не понятно где смотреть почему она не хочет устанавливать связь). Короче, поставил Mobile Partner и вроде как жизнь наладилась.