After some trial and error I finally got my Sansa Clip to recognize playlists (m3u). I did this using EasyTAG on a Debian box. The EasyTAG version used was the one which ships with Debian Unstable.
Thought I would document it here for someone who might need it.
Steps I've followed:
1. Connect the Clip to the PC in MSC mode(this is default in Linux).
2. Open EasyTAG and browse to the music folder of the Clip. In my case it was /media/SANSA M340/MUSIC. ( I had just one folder under MUSIC and it was named 'Running Assorted' and it contained all my music files). Your music collection should show up in the midle pane.
3. Select the Files you want to create into a playlist in the middle pane of EasyTAG. (You can also make ID3 tag changes to the music files if you want)
4. Once selected, Click on the 'Write Playlist' icon in the toolbar (third from right).
5. The 'Generate A Playlist' window should now pop-up. This is the important part , ensure the choices you make here are similar to mine.
5a. M3U Playlist Name : Choose "Use mask" and give it a name. Example: "test" ( no need for file extension)
5b. Playlist Options: Ensure "Include only the selected files" is selected.
5c. Ensure "Use relative path for files in playlist" is selected.
5d. Ensure "Create playlist in the parent directory" is selected.
5e. Ensure "Use DOS directory selector" is selected.
5e. Playlist Content: Select "Write info using filename".
6. Click on "Save" button.
7. You should now have a playlist file named test.m3u in the MUSIC folder.
8. Unmount the device and check if the playlist is showing up now.
NOTE: Sometimes the 'Refresh Database..' doesnt work and the playlist might not show-up. Ensure that a DB refresh happens when you disconnect from the PC.
EasyTAG is available as Free Software for Linux and Windows (http://easytag.sourceforge.net/) . I haven't tested on windows. If you have anything to add please do so..
http://forums.sandisk.com/t5/Sansa-Clip-Sansa-Clip/HOWTO-Creating-m3u-Playlists-using-easyTAG-on-Linux/m-p/33500/highlight/true#M21778