Do you by any chance have Auxo installed? I had the same issue (not with a Lexus) and what I had to do was restore the iPhone, pair it, jailbreak, and then install Auxo.
If you DO have Auxo maybe you can uninstall it and then pair.. not sure.
It most likely is something to do with the jailbreak though, unfortunately you can't restore it now without losing the jailbreak :/
Very interesting. I do have Auxi installed. I will uninstall it and try again. If not, I may just restore the phone. Thanks!