I don't know if this is your issue or not, but I had a similar issue, with no apparent cause. My Evo would do exactly what your's does. I resolved the issue, by first going into running processes, and stopping anything to do with bluetooth.
This allowed me to finally "unpair" my Uconnect in my dodge. Essentially deleting the Uconnect from the Evo. Then you will make a new connection with your car's BT and right after pairing is complete watch the screen of the Evo and a quick pop-up will ask about "always make this connection" or "always trust this connection" just click on the check box, and make sure the green check mark appears.
Strange enough now, after 4 days I have connected every time I enter my dodge, but under the advanced tab in the bluetooth section, it still says "paired but not connected" but if you look closely at the bluetooth symbol in your top bar, when it is connected it will have the 2 little arrows in the middle of the icon. Hope this helps.
