The HxM uses a com port. Try search again for a new device in "bluetooth settings" of the samsung. When it finds the HxM you see "serial port" . In my HTC that is com port 5. Select the same port in "Rungps" and it should work. Its like the good old days of computers: com ports do the trick. See page 63 of the manual.
I have the Zephyr HxM. I was able to pair the device to my Samsung Blackjack II, but Run GPS is unable to connect to the HxM. Any ideas, or settings the community has tried to get this connected would help.