as the previous poster mentioned: check the internet connectivity (use firefox e.g. to see if you can reach websites). If that is working, it might be that the mirror Yum is using is not synched with the Fedora servers.
You can change the default mirror, by editing the yum configuration (in /etc)
Yum is rather slow on first use.. (it needs to create db of the current packages, and seek for a speedy mirror for you)
Better said, in general Yum is slow compared to competitors.
during my fedora 11 period (currently on Slackware) i had the same problem. Eventually it began to speed up more and more.. but it took a while before that happend.