"In 2003 I had a problem setting up Bluetooth in Ubuntu, so I'd rather stick with Windows, thanks."
And as I think about it, I think I did get to the same spot as you, with the device 'paired' but not really. My theory now is that bluetooth works on a controller/client relationship, and that both your laptop and phone are trying to be controller and are thus incompatible with each other, while things like headphones would be clients. Would love to know if someone more familiar with bluetooth could correct me.