Correcting iTunes playlist music file paths

An iTunes-for-Windows user, I recently moved my music to a new PC and I reorganized my music by artist. After I reinstalled iTunes, I found that my extensive playlists had been lost. I was able to restore many of them by shift-double-clicking on the iTunes icon, choosing Library and pointing to an "iTunes Library.itl" file restored from an old file backup. However, most of the songs in the playlists have exclamation marks due to changed paths.

How can the playlists best be corrected for the new music file paths? Should I move all the music to a single folder? How would I later restore the music to the folders they're currently in without disrupting the playlists?

Any suggestions would be appreciated.