iTunes: The song could not be used because the original file could not be found. Would you like to locate it?
Have you tried consolidating the files? Go to "File" -> "Library" -> "Organize Library" -> "Consolidate files". Afterwards iTunes should know that none of those songs are on your disk.