Unfortunately, frankz is right that your best bet, if there's not a solution with relink music paths, is to batch edit m3us. You might be able to change your playlist format type and get them converted faster. I'm not sure, though.
You know, another thought that occurred to me if that if you have the files organized in a way that coincides with the playlists, you could potentially make auto-playlists based on folders or something.