Some info that may help
I have the same problem. I have a Samsung Focus as well. I get the same results when connecting to my 2012 Optima. I tried a few different Windows Phones; three or four Focus phones and an LG Quantum. I bought the car after I had upgraded to Mango (WP7.5) and never was able to get the phone to stay connected except for the first pairing. My dad had a Focus that was still on WP7 and his connected and worked fine. It always connected every time he got in my car. About a week or so ago I finally noticed a pattern with mine. It would connect and work once in a while but I didn't know why. I realized it was when I was on a call. I started calling my voicemail when getting in the car to test the theory and, sure enough, it worked everytime I was on a call. After doing that a few times I didn't care if it connected so I didn't call voicemail but it connected and worked anyway. My phone has since connected and worked great every time I got in the car for over a week.
Until yesterday. It did connect but I tried to listen to music over bluetooth but the car says bluetooth audio is not available. I reset the UVO system and deleted and re-paired my phone and everything worked, even bluetooth audio. Of course, turning off the car and turning it back on left be back where I had started. The phone connects for 10 or so seconds and then disconnects. I'll try the calling voicemail trick again on my next few drives and see if that gets be back to a reliable working phone connection (without bluetooth audio).
My parents just bought a Ford Explorer with their UVO equivalent. All our phones pair with it and reconnect on subsequent drives with no problem at all so I don't know if this is a UVO problem or a Windows Phone Mango problem.