Well, the nuclear option seems to have worked. All my apps and stuff are still being downloaded from the backup, so I'm reluctant to try to download thousands of songs at the moment. However, the one test song I tried worked. I couldn't download it previously but got it to download just now.
I will report back after my back up is completely restored and I can stress it by trying to download a ton.
EDIT: having the same issue now, not clear why. I can't seem to swipe delete songs individually for some reason. Went into iTunes Store, more, downloads as suggested. It shows 1900 items there (!) so they are now downloading... I hope.