For what it is worth, I've paired 2 different phones w/ my truck (XLT, basic Sync). The first was an HTC One X. Worked perfectly -- paired on its own every time I started it up.
The second is an LG Optimus. Won't connect on it's own -- I have to manually open bluetooth every time and have it connect. Sometimes, it pairs only to audio, sometimes to audio and phone. If I'm in and out of the truck running errands, it will often stay connected, or will connect if I ask Sync to do so, but it isn't great. I've re-paired several times.
I don't know if it is the phone or what. I have a lot of bluetooth devices, from speakers to gps bike computers to headphones to I don't know what else. Some of the bluetooth devices worked better w/ the HTC, some have worked better w/ the LG, some work equally well with either. FWIW, though, they both have worked great w/ my Chevy!