Oh boy... this has been an issue for me since I first bought a Windows Phone over two years ago. I've tried everything and I have a help thread open on Microsoft Answers That's over 9 pages long... with no real answers.
There are actually multiple ways to make this work, but most are just not feasible with my large collection (over 13,000 songs).
What I've done is use Xbox Music on my Windows 8 PC that has all my songs. I've manually made a few small playlists on Xbox Music that then automatically sync via the cloud to my phone (make sure you select 'keep offline' in your phones playlist settings, because some songs will need to be downloaded as sometimes they aren't recognized even if they're stored in your phone).
For the larger, more complex playlists, I made them in Windows Media Player and they were found by Xbox Music (be sure the playlist file is stored in the same music folder that Xbox Music is set to search). These playlists will also cloud sync automatically.
Honestly, it seems as if they make it as difficult as possible because they want you to use the cloud and streaming through the Xbox Music service completely.