It looks like you have to have your phone on, not screen timeout, to get it to automatically connect to bluetooth. I still have more research to do on this. When the phone asks if it can download contacts to your car, make sure you check off, DO NOT ASK AGAIN. Good luck. Post solutions.
I have a Verizon S3 and a '10 Jetta TDI with factory bluetooth (phone only, no audio streaming) and I have replicated that if your screen is on then you auto connect, if it is off then I have to open the bluetooth settings and connect manually.
But a problem I have found that drives me even more nuts... When I am connected to my cars bluetooth and I have an aux cable plugged into the S3 to listen to podcasts, etc. If a call comes in and I am not listening to anything on the S3 then when I answer a call it tries to go thru the aux cable and the toggle button on the call screen is greyed out - I have to pull the cable out then BT kicks in! If I am listening to a podcast or music then the BT works fine.
Definitely a bug. I am going to call VZW today about it.
i have a verizon s3 and it auto connects just fine to my bmw and to my griffin bluetrip.
There's definitely something off with the BT profile on this phone. It works fine when I only connect for phone and it will autoconnect every time. However, if I try to check both boxes for audio and phone it will work that one time and then need to be connected manually each time after that. Very odd.
I have a 12 Maxima that had no issues with either my 4s or DX.