These things can be a bit flakey.
My Arduinos talk perfectly to my laptop via bluetooth. It is the only communication I have with them at the moment.
My dumbphone can pair with Arduino but cannot do anything.
My Android tablet with BlueTerm can pair with Arduino but cannot do anything. That is very disappointing. I have not persued this as my laptop is fine and hardly less convenient than a tablet, and the tablet is really junk.
My desktop can see my phone and my tablet but cannot see the Arduinos.
In short, all the problems lie with the peripherals, not Arduino.
I fail to see the need to use software serial library to get UNO and bluetooth to communicate. I don't think anybody else does. I only use bluetooth for data aquisition, but no extra software of any sort is required to do this.