Originally Posted by coney

You will need to make the phone discoverable. By default the Bluetooth is on, but the phone is not discoverable until activated.
Go to Settings>bluetooth. Then tap on the top line, which will be whatever your phone is called and it will change from only visible to paired devices to Visible to all nearby BT devices. This will time out, which you can change in the menu tab on that screen.

I had no problem setting mine up for the BT phone in my Mazda.

Think you may have got past this though. I'll leave it here for others though.
I used to sometimes get a problem with my old HTC on BT compatability with other phones. Might be that. Try a reboot of the phone.