I wrote last year about how to use bluetooth networking to connect to the internet via a mobile phone. Since then, I had heard rumours that NetworkManager was now able to do this as well, but I actually never managed to find out how to do that (admittedly, I never looked too hard).
Today I checked again.
Since those are the "reference implementations", I started GNOME's nm-applet and bluetooth-applet instead of knetworkmanager and kbluetooth. I still could not find anything related to bluetooth in nm-applet's UI. Then I looked a bit farther and found Dan Williams' post about it.
Long story short: I deleted my phone from bluetooth-applet's "known hosts" and re-paired it again. There it asked me if I want to access the internet via my mobile phone, which I confirmed. After that, nm-applet has now an entry for "PANU" which is the Phone's connection.
Working well and pretty cool, too. One more workaround that's not needed anymore.
For completeness, I also tried to remove and pair the phone with kbluetooth, but apart from it not working at all (never asking for a PIN), it also did not ask for the internet connection stuff. So for now, if you want Bluetooth networking, just use nm-applet and bluetooth-applet.