Give us some background on your setup (in advance always helps if you want speedier resolution). For example, if you have media on an external drive and do not turn on the drive (or the drive is sleeping) before starting iTunes, iTunes will see the files as misssing. If you turned on the external after starting iTunes, iTunes will not have a second look until you try playing the track, then it will find it and play it.
Unless you see a file actually downloading from the Cloud it isn't coming from there because the Cloud doesn't stream to computers.
Another way to fix the links is to say yes when it asks if you want to fix one. Find the actual file on your computer which it needs to play (in your iTunes media folder), then say yes when it asks if it should find others.