Bluetooth device not listed for PAN/DUN internet connection despite paired, connected

Greetings, I recently upgraded from Ubuntu GNOME 14.04 to Ubuntu GNOME 15.10.

Sometimes I use my Bluetooth-enabled phone for its internet connection.

In previous Ubuntu GNOME 14.04.3, this used to work:

1.) Enable Bluetooth on Ubuntu and on phone
2.) Open top-right Gnome3-shell menu on screen (the one with wireless icon, speaker volume icon etc.)
3.) Top-right menu shows Bluetooth
4.) Select Bluetooth -> Bluetooth settings
5.) Scan for devices
6.) Pair with it, entering PIN code etc.
7.) Connect with it, confirm connection request on phone -> status paired, connected

Then, following steps would be:

8.) Top-right menu shows "My phone" together with "Wireless network" and "Battery".
9.) Select "My phone" -> "Use it for internet connection"
10.) Set up wireless provider etc.
11.) Internet connection is now possible over Bluetooth via phone. Success.

But in new Ubuntu GNOME 15.10, I cannot take steps 8 to 11. I am stuck at the following:

8.) Top-right menu does not show "My phone", only "Wireless network", "Bluetooth" and "Battery". Bluetooth entry only shows "1 device connected", but I do not see any option for addressing my phone via this menu and making an internet connection with it. Also in the System settings -> Bluetooth, when I click on my phone, I see no mention of it having a dialup/umts modem inside.

Am I doing something wrong?

I tried running bluetoothctl tool:

[My phone]# info
Device XX:XX:XX:XX:XX:XX
 Name: My phone
 Alias: My phone
 Class: 0x5a020c
 Icon: phone
 Paired: yes
 Trusted: yes
 Blocked: no
 Connected: yes
 LegacyPairing: yes
 UUID: Vendor specific (00000002-0000-1000-8000-0002ee000002)
 UUID: Vendor specific (00000004-0000-1000-8000-0002ee000002)
 UUID: Service Discovery Serve.. (00001000-0000-1000-8000-00805f9b34fb)
 UUID: Serial Port (00001101-0000-1000-8000-00805f9b34fb)
 UUID: Dialup Networking (00001103-0000-1000-8000-00805f9b34fb)
 UUID: OBEX Object Push (00001105-0000-1000-8000-00805f9b34fb)
 UUID: OBEX File Transfer (00001106-0000-1000-8000-00805f9b34fb)
 UUID: Audio Source (0000110a-0000-1000-8000-00805f9b34fb)
 UUID: A/V Remote Control Target (0000110c-0000-1000-8000-00805f9b34fb)
 UUID: A/V Remote Control (0000110e-0000-1000-8000-00805f9b34fb)
 UUID: Headset AG (00001112-0000-1000-8000-00805f9b34fb)
 UUID: Imaging Responder (0000111b-0000-1000-8000-00805f9b34fb)
 UUID: Handsfree Audio Gateway (0000111f-0000-1000-8000-00805f9b34fb)
 UUID: Vendor specific (00005005-0000-1000-8000-0002ee000001)
 UUID: Vendor specific (00005601-0000-1000-8000-0002ee000001)
[My phone]# register-profile 00001103-0000-1000-8000-00805f9b34fb
Unable to find GattManager proxy

Is maybe some dbus service not running (GattManager)?

But it generally does support the dialup networking profile - it already worked in Ubuntu GNOME 14.04.

How does the top-right menu know, which network access methods are available at all, which entries to put into this menu - maybe something is missing there?

gnome-bluetooth is installed.

Not sure if to file this under Distribution Ubuntu in general or under project "Ubuntu GNOME".

Please help.

Greetings