I'm having the same problem...along with the following:
When I go to to play anything I downloaded from the marketplace, I get "the item is missing or can't be played" and then it proceeds to go display, one by one, all the songs after the one I want, in alpha order.
So, the songs are all in the zune (according to the "storage" section and my listings on the zune) but none of them will play.![Sad [:(]](/emoticons/emotion-6.gif)