I'm assuming you've done the hard reset and that didn't help?

Do you have another BT phone you can test your BT250 with? If other people can get it to work (and since there are no parameters to twiddle, and since you're obviously doing all the right things) maybe the headset...

One other thing, are you just unable to pair, or can you pair and it works badly, or does it just plain not work?
E