Ok, downgrading to the following versions worked for me: libnm-gtk0 0.9.8.2-1 libnm-gtk-common 0.9.8.2-1 network-manager-gnome 0.9.8.2-1 gnome-bluetooth 3.4.2-1 gir1.2-gnomebluetooth-1.0 3.4.2-1 libgnome-bluetooth11:amd64 can be removed (I didn't realize they where in the brackets in message #10) I got the packages from: http://snapshot.debian.org/