Wahnsinn! Ich habs gelöst.
Nur leider weiß ich nicht genau was genau das Problem gelöst hat.
Es standen im Log-File viele Fehlermeldungen, die vom Bluetooth ausgingen.
Ich habe nochmal die Pakete geprüft und festgestellt, dass gnome-bluetooth10 drauf war (ich glaube das gehört zu Gnome 3.4).
Das habe ich gelöscht und das aktuellere gnome-bluetooth11 installiert. Beim Neustart war erst wieder das selbe Problem, dann habe ich wieder Gnome-Session gekillt und mich nochmal eingeloggt und plötzlich hat es funktioniert.
Vielen Dank für eure Hinweise.
Das Problem ist gelößt.
Grüße
Max