This issue is popping up a lot now with different car makers, headsets, etc...the only common denominator is GS4. It probably has a bug that needs to be corrected by an update.
In the meantime, there are folks recommending a bluetooth app from the Play Store. I have not used it myself (will try when I get to my car later) so I don't want to recommend it just yet, but thought I could mention it. Check in another thread about bluetooth music for more details.