gontomoさん返信ありがとうございます。
今使っているヘッドセットはhttp://www.pro.logitec.co.jp/pro/g/gLBT-HP110C2BK/です。
自動接続をしたい訳ではなく、いちいちデバイス削除→新規登録をせずにBluetooth接続をしたいです。
Windowsや携帯ではできているので、Ubuntuでもできないことはないのではないかと思っています。
方法はありますか？

私の#2とhiropackさんの#4は根本的には同じことを説明しているんですが、同一プロファイルに対して１つのペアリングしか保持できないのがシングルペアリング、複数のペアリングを保持できるのがマルチペアリングです。

現況の説明としては#4の後半に書かれていることが当てはまるのではないかと思います。
たぶん、携帯とペアリングをするとHSP(or HFP)とA2DP(+AVRCP)の２つのプロファイルでペアリングされてしまっているのではないかと。
この状態であれば、Windowsであろうと、Ubuntuであろうと、当該ヘッドフォンを使おうと思ったら再ペアリングが必要なはずです。

逆に言えば、携帯はHSP、UbuntuはA2DPとプロファイルを分けてやればご希望の状況を作り出せると思います。

--------
補足
ペアリングというのは、単に機器同士の登録を行っているだけではなくて、ペアリングを行うことで通信に使用する暗号キーを双方で取り交わします。
シングルペアリングというのはその暗号キーをひとつしか持てない機器、マルチペアリングは複数持てる機器だと思ってください。
シングルペアリングでは１つしかキーを持てないので、UbuntuでペアリングをしたあとにWindowsでペアリングをすると、Ubuntuで取り交わした暗号キーが失われてしまいます。
また、暗号キーはペアリング操作毎に異なるものを発行するので、一度失われた暗号キーは二度と発行することができません。
このため、シングルペアリングのデバイスでは接続先を変更するたびにペアリングをする必要が出てくるということです。
--------