How can I recover lost playlists on itunes from the Ipod?

There are a number of third party utilities that you can use to retrieve music files and playlists from your iPod. You could start your research with this one which advertises playlist cloning among it's functions: iPod Access Mac & Windows (iPhone and iPod Touch compatible)

You can read reviews and comparisons of some others here:
Wired News - Rescue Your Stranded Tunes
Comparison of iPod managers

I found this in the CopyTrans http://www.copytrans.net FAQ:

Question: My songs are already on my computer and I want to back up "just the playlists".

Answer: CopyTrans actually doesn't allow you to backup "just the playlists".
Though, thanks to the incremental backup, performing a backup when the songs are already on the computer should only import the playlists except if the first backup was not made with CopyTrans. In this case, performing a backup on an existing library will probably generate duplicate songs.
The best way to import the playlists of your iPod to your computer is to empty the iTunes Music folder on your computer (ONLY IF YOU ARE SURE ALL YOUR MUSIC IS ON YOUR IPOD TOO) and perform a full backup to iTunes which will transfer both the songs and the playlists to iTunes. Once this is done, you'll be able to enjoy incremental backups that only update iTunes based on the recent changes on the iPod.

Utilizing your suggestion, could I just move my music out of the iTunes Music folder to somewhere else and then copy the songs and playlists on my iPod classic back to my computer to restore my (lost) playlists? And could I then move my music back into the iTunes Music folder and that way have ALL my music AND my playlists?

If you simply create an On-The-Go playlist with each of your playlists on the iPod, the playlists will sync back to iTunes.

Go to Music -> Playlists.
Scroll to a playlist and press and hold the center button. The playlist name will flash 3 times.
This adds it to the on the go playlist.

(from the iPod classic manual)
"*To save the On-The-Go playlists on iPod classic:*
Choose Music > Playlists > On-The-Go > Save Playlist.
The first playlist is saved as “New Playlist 1” in the Playlists menu. The On-The-Go playlist is cleared. You can save as many playlists as you like. After you save a playlist, you can no longer remove songs from it.
*To copy the On-The-Go playlists to your computer:*
If iPod classic is set to update songs automatically and you make an On-The-Go playlist, the playlist is automatically copied to iTunes when you connect iPod classic. You see the new On-The-Go playlist in the list of playlists in iTunes. You can rename, edit, or delete the new playlist, just as you would any playlist in iTunes."