So I went to the Verizon store and I believe it is the HTC Incredible that is at fault. Here is what we tried.
1) (Pass) Connected my BT-Q890 to the store's Motorola Droid and used Googoo's "Bluetooth GPS" to successfully talk to the BT-Q890.
2) (Pass) Connected via bluetooth my HTC Incredible to the store's Motorola Droid and initiated a file between phones. We did not run the file transfer to completion but the communication appeared successful.
3) (Fail) We paired my BT-Q890 to a second HTC Incredible unit owned by the store. Googoo's "Bluetooth GPS" could NOT connect to the BT-Q890.
I think this indicates that in general my HTC Incredible can use its Bluetooth, but that it has a specific problem with the BT-Q890. It also suggests that all HTC Incredibles might fail to work with the QStarz GPS units.
I wonder if HTC changed the implementation of the Bluetooth stack for Sense UI. Here is one thread that suggests HTC did such a thing for the HTC Desire, which I think is closely related to the Incredible (
link). They might have disabled Serial Port Protocol (SPP) in their Bluetooth stack, and I think that the BT-Q890 communicates using SPP.
Here are the Bluetooth protocols that the manual says the HTC Incredible supports: Bluetooth® 2.1 with FTP/OPP for file transfer, A2DP for wireless stereo headsets, and PBAP for phonebook access from the car kit. No mention of SPP, which is what I think the GPS uses...right?
A question: are there any newer 5hz GPS units that communicate via a different Bluetooth protocol? Maybe a different unit/protocol would be able to connect to the Incredible?
Otherwise I might need to wait for someone to root the Incredible so that I can use the Nexus One BT stack.