I have same reoccurring bug on two separate WP8 devices: Lumia 520 and HTC 8s, both updated to GDR3.
Namely, playlists synchronized from PC (either by WP8 soft or WMP) randomly disappear from my device. Files are still present, playlists created on device as well, but synchronized playlists are gone.
It mostly occurs after: - power off (be it forced or automatic) - two days
Longest time I had synchronized playlist on was about a week, and it even survived major software update (one of GDR's), but even that little brave playlist got murdered by this evil bug. It happened on all GDR's without any third party software that uses media. SD cards were tested and were healthy and properly formatted. Quick google search for "wp8 playlist disappeared" will show that it is not just issue on my devices.
Is there any way to make synced playlists stay with me forever? Or... is WP 8.1 a fix for this issue? If so then I might as well get it now (I am lazy so I decided to wait for official release for my language/provider/device).