Weird Bluetooth Behavior, difficulty reconnecting to paired device - Galaxy S II
I have similar issues with some headphones on my Galaxy Nexus, though it is only intermittent. While I do not have an actual solution, I have found that turning Bluetooth off and on again while the headphones are on is much quicker than navigating all those submenus, and does cause the headphones to reconnect.