What sort of computer do you have? On a Mac, you can use Senuti to get your tracks and playlists back into iTunes quite easily. From there it should be easy to sync them onto the new iPod.
If the iPod is set to manually sync with the computer then the playlists may be out of whack. iPod.Copier might be something that can help get the playlists back onto a PC.