Bluetooth GPS Receiver problem

[maraneric]

I just got my phone yesterday, and I am trying to pair my Visiontac VGPS-700 bluetooth gps receiver with it. However, when I click "Add new device...", the receiver is not found. If I try to do it in Telenav, a device with the mac address as a name is found, but the receiver does not show that it is successfully paired. GPS doesn't work either. The receiver works fine with my Treo 700p.
I know that bluetooth is working okay because I can find my Treo and my computer.

Does anyone know what could be going wrong here, or what I can do to fix it?