https://bugs.archlinux.org/task/35695 to get tethering working. Only works when adding the profile with bluedevil to networkmanager and then connecting with the "current" kde networkmanager applet. The gnome control center bluetooth thing has a button to connect, but the button is disabled. On blueman I get a timeout when trying to connect.
Does nobody find it sad that on desktop linux bluetooth tethering has been broken for a few years now and nobody cares? No really, install a default ubuntu 12.04 LTS, get a standard android smartphone and try if you can even pair it. Last time I tried it both the default ubuntu bluetooth thingy and blueman failed...
Your best bet is really, on the command line, pairing with hcitool, then sudo pand -n --role PANU -persist 30 -c bluetooth-id; sudo ifconfig bnep0 up; sudo dhcpcd bnep0
Just in case someone needs it.
To the people who don't believe that the "current" kde networkmanager applet is broken: Add a bluetooth tethering connection to the networkmanger. Open the knetwormanager administration/settings. Notice the tab "mobile broadband". It has a nice button "add connection" where you can add a cdma or gsm connection. Now remove the tethering connection. Now the "mobile broadband" tab is disabled and you have no way of reaching the "add connection" button anymore and your only chance is to add the bluetooth tethering profile with bluedevil.