Happens all the time for me too, I have found no way to fix it as I belive playlists is missing from the backup. So you have to roll back or make a new backup.
Hopefully this is fixed in MC12, there should be a check that the backup is complete so you can get a warning when you have a bad backup.
That really shouldn't be happening "all the time". I believe I've had that particular issue once in the past 2 years or so (and it was with a much older version of MC). Are your library files shared over the network or anything similar that could be causing the playlistx.jmd file to be "in use" when it tries to write out to the file?
As far as the backup situation... I just back my library files up myself using a simple script (part of my network sharing system). It archives the library files to a ZIP file once every 3 weeks, and always keeps a backup copy of "yesterday's" library at the ready. This system has protected me effectively for quite some time...
I don't have the current versions posted yet,
but if you check this thread out, and take a look at the BAT files, you should be able to get the idea...