From this discussion https://discussions.apple.com/message/16977127#16977127 the pairing is reported as possible.
Pairing of your iPhone with other iPhone was not successfull. May be not done in the right way.
iPhone pair with many BT devices without any problem. I have Samsung Headset and they work.
I would suggest you go the the shop and ask them to try with an head phone or let an Apple store check your BT.