Hi andya, I had the exact same problem! (Well not exactly, I don't happen to own an Infiniti, but I do have a bluetooth headset...) Anyhow, I got the 700p about 2 weeks ago, so excited, and went to pair my scala-500 headset to it, and it didn't show up. I'd just assumed that it was because the day before I accidentally sent my headset through the washing machine

so I helped myself to a new Motorola HS850. Got that home and tried to pair it, didn't show up at all on my 700p. Tried pairing it nad my squeaky-clean headset with a friends phone and they both worked great, so I knew that both headsets were fine.
Called Verizon, then Palm, then back to Verizon who easily agreed to send me a refurbished 700p. I've had the new one now for about a week and bluetooth works great on it! It sounds like my issue isn't an isolated incident, maybe some bad firmware like you said.
The only issue I'm noticing now is that after a few calls without the headset, the bluetooth will refuse to connect again to my headset. A soft reset fixes the issue, but it gets annoying. Any thoughts?