I've had very similar problems to all, been searching the forums for an answer, think I've got it via apple tech support:
see this link:
http://docs.info.apple.com/article.html?artnum=93313
to avoid the blah-blah-blah, search discussions for my name, if you're interested on the details of my specific problem.
now, the caveats post-process: virtually all music that was listed in the playlist sidebar folder "purchased" under "store" was deleted from the list. the songs are in the library, but it appears that the record of purchases is gone. also, the field "date added" was replaced with today's date (date of following the link procedure). so, no telling what's new or old...
at first, I was shocked (to say the least) to think that my purchased music was gone after following these steps; it's just the listing, however (I happened to have saved all the confirmation emails, and I've spot checked to verify that purchased music is still in the library).
hope this helps all who are dealing with this issue - I've been quite upset the past few days thinking that my 1200+ iTunes purchased songs were gone.