This is usually a problem with the X server not using the correct RgbPath, which was changed starting with FC5. Look in your /etc/X11/xorg.conf for a line like this:
Change that line to use the new location:
You'll have to restart X for the change to take effect. Emacs should then be able to figure out the correct definition for the color black. The /usr/share/X11/rgb.txt file contains all the definitions of the colors, in RGB format. Note that you don't need the .txt extension when putting that filename in xorg.conf (in fact, putting the .txt extension there will cause it to not get read).