I had the same issue for awhile and I gave up on it. I just recently got up and decided to do something about it, googled it and saw you guys had the same issue. So it gave me motivation to figure it out again. Eventually I figured it out. Hopefully the same steps work for you guys. Not sure what fixed it because I tried two things before I went back to Itunes to reattempt.
My goal was to try to delete cookies. Being new to Mac. I didnt know what i was doing. I ended up erasing my safari history before I figure it out. The second thing I did was go to Safari, Click on Safari (top right) and hit "Reset Safari..." Gave me a few options here. I selected "Clear History, Reset Top Sites, Remove all website data, Clear the downloads window. I went back to Itunes and my first attempt to redownload a song pop up a notification that I had a preorder available to download.
I hope this helps you guys like it did me.