Well, I got the replacement headset from Amazon… which had exactly the same problem as the first one!

I called Logitech this time, and talked to a guy called David who was really helpful. We went through the process of pairing, connecting etc. Tried turning off anything else bluetooth in the area (i.e. phone and iPAQ); nothing worked. Apparently there is a known issue with their Mobile Phone Suit software that can cause a similar problem, but I wasn’t using that anyway, so that wasn’t the case.

After trying everything we could think of, David checked the product number (on the barcode) and apparently mine was one of the original release ones. They have upgraded the firmware since that model to make multiple-pairings and different profile support better. I’ve sent back the headset (to Logitech in CA this time), at my expense ($12.50!), and they’re apparently going to send me one of the newer models to see if that will work, so fingers crossed.