Not sure who else has this problem, but I have a lot of my own songs (legal of course, Amazon downloads and CD rips) and playlists on my PC (Windows 7). I also wanted those playlists on my phone. With WP7 and Zune that was super simple to do and keep in sync afterwards. But the WP8 app that's recommended for my new WP8 Lumia 920 is terrible, so I'm using Window Media Player. The first time I created a playlist and synced it to my phone all was well. But then after going back and adding/deleting songs from the playlist on my PC and then trying to re-sync the songs would sync but the playlist would not update. Very frustrating.
After a couple hours online with Microsoft chat support last night (to my surprise the rep was actually some kind of help) we found a workaround. Create a new playlist by a different name and then it syncs fine again. And creating that playlist isn't as hard as it sounds. I just load up the current playlist that I've updated and failed to sync, start playing it so it's in the "now playing list" and then go to "File" -> "Save Now Playing List As..." and save it under a new name. Then sync that newly created playlist, boom it works!!
Yeah sucks that you have to rename the playlist, but it's 100 times better then re-creating it by hand. Hopefully Microsoft fixes this at some point in the future.
Hope that helps anyone who has experienced the same issue.