Bluetooth-пары с наушниками, но соединение с Audio Sink отказалось

Попробуйте установить linux backports для беспроводной связи:

sudo apt-get install linux-backports-modules-wireless-2.6.35-22-generic && sudo apt-get install linux-backports-modules-wireless-maverick-generic

restart