I wasn't going to suggest this because I know it's not much of a solution, but I use Amazon.
After losing some much loved playlists when phones went the way they so often do, and trying 8Tracks but still having to recreate too much, I've resigned my music safety to either an SD card, like DreadNatty08 suggested, or, what I actually use on a regular basis, is the Amazon Player. After setting up the playlists there, I can sync them to any device.
Is it perfect? No, I'm sure that to start with, I lost files in the original tx to their cloud, and sometimes when I sync (or dl, actually) I can get a duplicate playlist with a number after it, but I just double-check & delete the old one. I actually enjoy my time in waiting rooms by opening the cloud player and editing (usually adding to) the playlist on my Prime, then I can dl the playlist (and any missing songs) to my Prime (Voila! Music on Prime!), my phone, my Windows 7 machine/media center.
For what it's worth, hope that helps!