EDIT: So I finally got this working:
1) To make Pulse Audio support A2DP, this package needs to be installed:
pulseaudio-module-bluetooth. But after that it's still not easy to make it work:
2) Gnome Bluetooth applet vs. Blueman:
- I have not been able to make this work reliably with Blueman, but I found that it does with GNOME BLUETOOTH APPLET. I came across this solution when I decided to use Gnome Shell (3.4 at first) on my Lubuntu, which of course came with the Gnome Bluetooth applet (package name: gnome-bluetooth: If you decide to install it without the Gnome Shell, note that it will pull some gnome libraries it needs to work).
- I removed the troublesome Blueman and paired the devices via the Gnome applet, which led to successfully streaming A2DP, Pulseaudio via Bluetooth. For this to work, BLUEMAN HAS TO BE REMOVED, else it will take control of managing all bluetooth connections. When I upgraded my Lubuntu installation from 12.04 to 13.04, Blueman was reinstalled and did just that, and things started working again after I removed it.
3) After installing it (I did via Synaptic) I restarted PA
but that may be unnecessary, try it in case you experience problems at first.
4) To make the connection with the Sennheiser headset, I need to put it in PAIRING MODE by turning it on and holding down the on/off button for a bit longer, till the LED flashes red and blue (as opposed to connection mode - rapid blue flashing - that would usually suffice for connecting the headset to a host device that already knows it: that doesn't work). Then, in Gnome applet (it should remember the headset after first pairing), click the "connect" button for the Sennheiser M100 .
5) You may have to go into Audio Settings and select the M100 as output device, but I get audio through the headset and not the speakers even if the system soundcard is still selected.
Hope this works for you, too, but still: When you buy bluetooth hardware for use with your Ubuntu (or derivative) system, try and find something with explicit Linux support, preferably open drivers!