TL;DR: Remove old paired devices! I just went through this this week with a 2013 Wrangler. Here's what fixed it for me: deleting the other bluetooth devices from the radio. It had my old iPhone and my brother's iPhone. Neither was anywhere nearby, but when I tried to pair with my new iPhone, it wouldn't work. I tried multiple times over multiple days. Finally, as a test I just removed the other 2 phones from the profile. It paired perfectly after that and has worked since.