When my Motorola HS850 successfully connected with a Treo 650 to which it has already been paired, the HS850 would play a very quick set of three ascending tones that lasted for about 8/10ths of a second. However, recently when the HS850 tried to connect, the Treo 650 would play a four tone sequence that sounded like notes played on a piano and lasted for more than a second. After that, there would be no connection between the headset and the Treo.
Some aspect of the data pairing the two devices apparently got corrupted. I was able to resolve the problem by following the instructions in the Palm Knowledge Base that called for deleting and re-establing the Trusted Device pair.
I was surprised to see this work because I thought I had tried this before and not been successful. Nevertheless, I got the devices to re-pair with each other and I'll have a lot more productive use of my Treo 650 for voice calls as a result.