this message shows up when you are using the web interface. Have you tried running yum from the command line? which version on yum are you using, 1 or 2 ? also do you have any repositories configured?
often, without the right information it can be difficult to figure out the problem.