this is a known problem, according to my conversation with zune tech support. The only work around, that I've found is not a workaround at all. Download the songs and, hopefully, you find another version of the same song available because the ones you already have on your pc and/or zune will show as in collection and your only option will be to buy the song.
I'm guessing (hoping) that there will be some kind of fix in the near future or, as has been mentioned, some form of sky drive music file to get the songs onto the wp8 devices.