Hi!
This should help:
Go to your Music folder, open "iTunes" and move all "iTunes xxx Music Library" files to the trash, except the "iTunes 4 Music Library.xml" file. Move that xml file to the desktop.
Open iTunes (there won't be any music displayed now). Select Import from the file menu and select the xml file from the desktop. The import will take a few minutes. Then all your music will be in iTunes again. Check if your problem still occurs.
If it does, repeat the steps above, but before you import the xml file, open it with TextEdit and delete the references to the files manually. Save the file and import it. Now everything should finally work again.
I hope that helps.