I am having exactly the same issue: after the upgrade, the connection is unusable. I tried my old Droid, and it worked just fine. There is no reason to allow this to go on, as it should be backward compatible. ( I have a 2009 Nissan Altima Coupe that I certainly like more than a stupid phone. I tried to insert a clause in my contract that stipulated if they changed the system to render features inoperable, my contract would be void, but I could have had better luck trying to get an ATM to bake cookies...)
Anyway, if they don't fix it, I plan to let everyone I know who is considering a phone to be wary of the Samsung...