Beg apple. It worked for me. Tell them you did back up your old library but it's broke/lost/stolen. They can only give you back whhats still avalible for sale and they do it only once!!! I lost over 1000 tracks and got 900& back after a pleading lengthy e mail to their customer support centre
"The stuff you bought from them should be downloadedable via a link somewhere on iTunes for purchased items. You may need to dig. Are you os5?'
It sounds like this is all sorted, but it's worth nothing that the link to get all your old purchases is a part of iTunes 10.5 which is available for both Windows and PCs. So even if you haven't got iOS 5 on your iOS gadget, or even if you're using iTunes without an iOS gadget, there's now a way to get all of your purchases from iTunes on your computer.