Hi, new here, just wanted to post somewhere a tip for those wanting to set up an internet connection over a phone's bluetooth teethering. Mine wasn't working and I spent several hours messing around with blueman, bluedevil, console, etc.
At one point I just tried the simple thing of changing the protocol setting in my phone from IPv4&IPv6 to IPv4. Now it is working fine.
In my particular case I am using Debian 8, a cheap bluetooth dongle from aliexpress, and no extra special packages.
This is very simple info, but I guess sometimes we get stuck on simple things, so maybe this helps somebody out there.
See you around!