you say you ahve tried windows media player playlists? I ahve no problems at all with WMP playlists. here are the instructions i use and done have any problems at all. honestly i tested M3U playlists as well and didnt see the issue. see my other posts in this thread. That said WMP playlists is the easiest way to go.
http://kb.sandisk.com/app/answers/detail/a_id/946/kw/creating%20playlists#sync_playlist
