The Handheld Sync tool is designed to do exactly what you said it tries to do: Transfer the music files *and* the Playlists together. For a lot of people, they will have music on their computer first and then use the Handheld Sync tool to copy that music, and playlists, over to their handheld device.
MC has a menu item to export playlists as just playlists. File > Export Playlist
This should copy a playlist file to your hard drive and you can then move that over to your handheld. The unknown part here is that the playlists normally use a file name to reference the songs. ...and the filenames of the files on your computer, and the files on your handheld are probably going to be different. At the very least the file path (directory structure) is probably different.
You might be able to make it work with a simple substitution in the exported playlists. Like using Find and Replace in a text editor and replacing C:\My Dir\Music with /SDCard/Music . That's just a made up example, but I hope you see what I'm trying to illustrate.
It might be easier if you just start from scratch on your handheld. Make sure you have ALL of the music from your handheld on your computer with MC. Then erase the entire handheld. Finally, use MC to sync one or more playlists, AND the music files at the same time. Then MC will be able to make the playlist files correctly.
There is probably another way of doing this too. Maybe someone else will have a clever idea or two.
Brian.