don't worry, you can still restore all of your playlists - if you have a backup of a previous library file.
Your problem is this: You rescanned your files, so MM created NEW database entries for all the files located in a new place - and you already deleted the OLD files which were assigned to a playlist from your library.
This can however be fixed.
You need to download and install this script: http://www.mediamonkey.com/forum/viewto ... =2&t=42085
Then you run it (Tools-Scripts-Restore/Synchronize Database), tell it where your backup library database is.
Then, you need to give it a bit of time - it will look at all songs in your current database and see if it can match them to songs in your old backup database - they should only differ in the location, but the tags/filenames etc should be identical. This script is smart as shit, and will even look at song length, file size etc etc to make sure it matches the right files.
Then you can tell it to put the new files (in your current library) into the same playlists as the old files were. Presto, done!
Oh, and if this script helped you out, you should consider donating a few euros to the guy who is maintaining this very important script... (I did - saved me weeks of work)