Same Issue.  On my old android phone the best solution for me was Songbird with the Folder Sync plugin.  Unfortunately Samsung Galaxy S3 only supports MTP mode and not mass storage mode, and folder sync will not work in MTP mode.

I have tried several desktop players and they all fail to syn playlists properly: Windows Media Player, Songbird, Media Monkey, and WinAmp.  They all have the same problem, they create the play lists in the playlist folder and if you click on them they look OK but when you open them in the phone's player no songs.

I did find an interesting post for creating .m3u files with a script and copying them to your music folder here: http://androidforums.com/samsung-galaxy-s3/583712-syncing-music-playlists-galaxy-s3.html

Turns out that Songbird + Folder Sync plugin will create the right kind of m3u playlists so you can stage what you want on your phone using Folder Sync then cut and paste it into the phones music folder using Windows Explorer.