I'm not sure about 904 but natty supports connection through bluetooth PAN out of the box via NetworkManager. You have to pair the mobile device with your computer using the bluetooth-application. After that the bluetooth device can be selected in the nm-applet as a network device. Maybe it's just as simple with 9.04.
Does this howto help?
http://ubuntuforums.org/showthread.php?t=598890
I'm not sure about 904 but natty supports connection through bluetooth PAN out of the box via NetworkManager. You have to pair the mobile device with your computer using the bluetooth-application. After that the bluetooth device can be selected in the nm-applet as a network device. Maybe it's just as simple with 9.04.