I've just been playing with Bluetooth on a similar device here in the office, and I noticed something I still see in WM6 - it's very important to know whether the BT accessory device requires a passcode or not. Some do, and some don't - and if you set the WM phone to NOT use an authenticated connection, but the accessory (such as a GPS receiver, etc.) requires a passcode, then WM won't actually tell you you've done something wrong - it just won't work. Vice versa, I believe.
I just had to fiddle with this for a bit in two places: You have to pair with the device, obviously, but you also need to make sure that the connection - whatever COM port you're using - is using the correct authentication, or lack thereof.
Perhaps in the hard reset process, the way you had your phone set to pair up (authenticated or non-authenticated) got reset as well.