First of all you have to install a new Bluetooth manager: Blueman. You can do it by adding the following to lines to your /etc/apt/sources.list
deb http://ppa.launchpad.net/blueman/ppa/ubuntu jaunty main
deb-src http://ppa.launchpad.net/blueman/ppa/ubuntu jaunty main
sudo apt-key adv --recv-keys --keyserver keyserver.ubuntu.com 6B15AB91951DC1E2
sudo apt-get update
sudo apt-get install blueman
this will remove Bluez and install Blueman.
Now you can start it at System -> Preferences -> Bluetooth Manager. You must select your phone here and then roght-click Setup -> DUN then right-click Serial Ports -> Dialup Service. After allowing to connect on your phone, the phone will shortly appear in the NewtorkManager.
To re-initialize an already configured device just right-click the applet-s icon and select under Recent Connections the Dialup Networking.