I had the same problem. I thought everything was messed up. I was quite upset. I called for help and was told to Exit the Zune software and rename my Zune folder (C:\Documents and Settings\USERNAME\Local Settings\Application Data\Microsoft\Zune) to Zune OLD. I was then told to open the Zune software and the database was recreated with all the correct data.
