I can't re-download a song with iTunes on my PC or iPhone
I had this exact same problem and I tried the same solution you did: deleted the file and could not redownload. It just said "Purchased" and there was no option to redownload. It turns out that I must have selected to "hide" the purchase. I fixed this by going to my account settings in itunes and clicking "view hidden purchases". Low and behold, my missing file was there. I clicked the "unhide" button and was able to download it again from the itunes store.