Default Bluetooth pairing weirdness

So my m8 was working great streaming to my car and while I was pairing a loaner car I accidentally deleted my real car. I didn't think it would be a big deal but man it's been rough. I get the car searching for my phone, click the scan button on the phone and the car shows up. The second I click it to start the pairing the car says pairing failed and the phone says the PIN number was incorrect. It's like the phone still has configuration data it's trying to use.

Any ideas? I haven't rooted yet and I would like to avoid doing a factory reset.