Have all repositories in yum.conf been uncommented and an update been run followed by a search for bsdgames first? There's fedora extras repository out on the internet along with freshrpms too and these aren't accessed by yum until they get uncommented in yum.conf.
