Connecting BlueSmirf to GPS keyfob

I have a BlueSmirf BT modem and a Qstarz keyfob gps. I want to use the modem to get the NMEA data so I can display it. A few weeks ago I hooked everything up with my UNO and everything worked fine. I tried again this weekend and the BT modem won't connect anymore. I just get a "Connection failed". I know the manual for the fob says I need to enter the "pairing code" or whatever that is, but I am sure I did not use that a few weeks ago. Any thoughts?

Update:
I am able to connect with my macbook, and get data from it, so it is not a general problem with the fob.
I might have to switch to USB.

Is a bluetooth device discoverable when it is paired with another device? In this case, since the fob is paired with the Mac, could that be preventing a connection even if the kfob is discoverable?