Sorry got an S3 here too, but when it first connected, it said on the phone "<Device. wants to access your contacts and details, Y/N" or something like that, with an option to "don't ask again". If I had selected don't ask again and then "N", than I suppose I'd never get contacts on the medianav.
Did you see anything like that on your phone the first time? Perhaps deleting the pairing and trying again to see if it does it?