Wouldn't it pay to just get a USB GPS
puck instead?
Frankly I'm a bit wary of using separate Bluetooth sources for GPS (usually dependent on
battery life in that device). I say that as I ran a BT GPS receiver years ago, supplying the data to my Nokia phone of the time, which ran great European maps (free download off Nokia), which were far better than my old
Garmin, with much better spoken directions (I only used speech directions on a motorbike, as you really didn't want a distracting
screen on your handlebars - both the GPS receiver and phone lived happily out of the rain in my tank bag).
I did have the GPS receiver
battery go flat a couple of times (and using your phone for GPS will hammer the battery very fast, even if in flight mode), so figured it was better(for me anyway) to have stuff driven off the same battery.
The USB GPS Sirfstar IV
puck is pretty
cheap too (about £28 for the one I just bought, to be plugged into the new
laptop when I get it).
Good luck getting it sorted though.
eta: I picked up a
cheap LG Leon phone when on offer before
Christmas, to check out Android 5. SPP is available with it running Bluetooth 4.1.
Hope that helps some.
eta2: You may have turned off permissions for the necessary data to be sent from the phone? What phone do you have, and what version of Android is it running, are probably the most important basics that need knowing?