yo utilizo la magic y el bluetooth de mi ubuntu sin ningún problema, eso sí sólo lo he usado para enviar y recibir archivos, no tenía idea de la existencia de gnome-phone-manager que dices.
Pero el punto que dices -la conexión- al menos a mi me funciona bien, y sin ninguna configuración en particular, lo agregué como cualquier otro equipo bluetooth y me lo reconoció