Ok... update: This device just does not work with the behold.
I took it to the t-mob store... the manager there tried to get it to work.... no luck... swapped it with another bluetooth unit off the shelf... no luck.... then he tried to get the bluetooth to pair to another samsung behold, but no luck either. Its worth noting he was able to pair the motorola bluetooth with 2 other devices no problem, just not the behold.

So, I returned it and got my money back for the headset. Clearly this is a behold problem. Sure wish there was an update.
I will try one more time to find a stereo headset that will work, but if not, then I'm returning the phone.
C'mon T-mobile / samsung... this is dissapointing.