I just took my Samsung Note 10.1 running Kit-Kat (4.4.2) out to the car and it works fine with one exception. For the first track, I get the correct track number (001), but when it goes to the second track, the track number on the headunit is one greater than in DSub. So the second track shows as track 003 on the head unit, the third track shows as track 004 and so on.
For the S3, I'll see if there is something about the custom ROM I am using. It's based on the last AT&T TW 4.3 release but there may be something in the customizations that changed the Bluetooth behavior.