If the following suggestions work, please let me know and you can Accept the answer (and if possible, leave positive feedback). If not, please DO NOT Accept the answer. Instead, let me know and we'll try some more things or I can refer you to another Expert who may be able to help you further.
If you do not have a backup of your purchased music, then it may be gone. In the good old days, Apple would allow you to download music more than once as long as you purchased it the first time. Now they have changed this policy to allow for downloading only once, then it is your own responsibility to make necessary backups.http://support.apple.com/kb/HT1469
Do you have access to a backup of the music at all? Even if it is on an iPod? There is software available to extract music from an iPod. Also, you may be able to recover the info from the old computer if the hard drive has not yet been reformatted. It depends on what happened to the previous computer. But that would be a different question all together. Sorry.
This is the info as it is directly stated on apple's site:
When you buy a song, video, iPod Game, or album from the iTunes Store you are entitled to download it a single time. If you want to download it again, you must purchase it again. You can copy downloaded content between authorized computers.
Important: Make a backup of the content you purchase. In case of data loss, including hard drive failure or replacement, accidental deletion, and so forth, you'll be able to restore it from the backup. See How to back up your media in iTunes for instructions.
Applications purchased from the App Store can be redownloaded free of charge by following the instructions in How to redownload purchased apps from the App Store.
As far as getting the music off of your ipod, you will not lose your music on your ipod unless you register the iPod to automatically sync with the new hard drive. Then it will overwrite the files on the iPod. If you have auto sync on the reformatted hard drive, or setup on the iPod itself, disable both through iTunes on the reformatted hard drive and through the menu on the iPod. If you do not have auto sync on, I suggest doing the following anyway, just to be sure:
While connecting the iPod to the computer, hold down the Shift + Ctrl keys in Windows. This will stop the iPod from auto sync’ing with iTunes and the iPod will then appear in the source list. Wait about 30 seconds to be sure the iPod has mounted, and that it will not auto sync, then let go of the keys. Right click on the iPod icon in iTunes’ source column and select iPod Options, then check the box that says “Manually manage songs and playlists”. You can now manage your library without losing any songs on the iPod.
What I would first suggest is using a program to remove the music from the iPod to the computer. Then when you have all of the music on your new computer, resync the iPod to it. This should solve the problem.
I suggest sharepod. This is a program (free) that will allow you to copy the files from your iPod to your hard drive. The program is pretty self explanatory.http://www.getsharepod.com/
As far as the playlists go, this would have been migrated over from the old computer. But if you've deleted the music, it is likely why the playlists are no longer available as well.
Good Luck and let me know if you have any other questions.