I had a similar problem recently when I rearranged my directory structure. After the restructure, all my playlists appeared empty.
Note that the playlists have the concept of active and inactive entries, but I've never seen a way to get Madsonic to export a playlist with all the entries, including the inactive ones.
So I created some symlinks in the directory, added a new folder entry in Madsonic to temporarily recreate the older file structure. After a rescan, I had double the song entries, BUT more importantly, all the older playlists were populated again. It looks like the playlists are rechecked at the end of the media scan process because the playlists didn't show populated until the scan was complete.
At that point I exported all playlists, removed the temporary folder entry in Madsonic, removed symlinks, deleted all playlists in Madsonic, recan and database cleanup. At this point I have all songs scanned, a clean database, and no playlists. Using a text editor, I edited the exported playlists to reflect the newly modified directory structure, then imported all the playlists. I had to use the Madsonic database editor to change the owner of the lists back to their original owner, but that was better than telling everyone that the playlists were lost (yet again).
My suggestion is to periodically export the playlists so you can edit them externally and re-import them when this happens again. However, I would have expected your playlists to be restored once the media was restored.