I was having the same issues with my 2011 Ford Fusions SYNC with factory Nav. After scouring the web for two days I was getting ready to return my Galaxy S2 LTE. I was unable to find any help at all (just lots of complaints) until I read your thread. I tried your suggestion and it worked perfectly. I had migrated from an iphone 3gs which also worked perfectly with Fords Sync and was considering an iphone 4s, but after using the Galaxy S2 for a few days I was ready to delete itunes. Forever.
Thanks to you, now I can.
This is a great phone.