Well, bluetooth connectivity has returned. I had some time last night, so I started going through some easy troubleshooting steps.
First, I tried connecting with my wife's iPhone 6, and it worked perfectly. So I knew it wasn't an OS issue. Next I disconnected the battery in my car to reset the stereo. Connected my phone with the same result as before. It showed some kind of false phone call, essentially locking up the unit. Next, I made sure I had a current iCloud backup, then restored my phone to new. Once restored to new, it connected as it should. Back in my house, I restored from my iCloud backup. Once up and running again, I tested in the car, and it worked just fine. Seems like there was some kind of leftover garbage from my previous phone or connection in the profile.
So ya, nuke the phone and restore from a backup. It worked for me! That said, There's obviously a bug causing the initial issue, so I hope it gets resolved in 8.0.1.
Thanks all!