Export your playlists, then delete everything from your library and add all your songs back (it helps to search for MP3's and AAC's in your designated music folder). Then either import your playlists, or open the file(s) in a text editor and add them back manually.
This will reset your play counts and probably your ratings, though, so don't do it if those concern you. If so, simply list the files by song name and start scanning. I would lock my music folder so iTunes wouldn't ask me if I want to delete the actual files each time, then use the arrow keys to scan for dupes.