All the playlists etc should've been saved in your old iTunes also. If you copied the entire iTunes folder you'd have the XML and settings files with all that information too.
There are several programs that allow you to recover music and playlists from your iPod
Try YamiPod - Free and comes in Win and Mac versions
http://www.yamipod.com/main/modules/home/