Can you please post the contents of your ~/.emacs ?
It might help in diagnosing your font problem.
For example, my ~/.emacs has the following as regards fonts:
;; custom-set-faces was added by Custom -- don't edit or cut/paste it!
;; Your init file should contain only one such instance.
'(default ((t (:stipple nil :background "#ffffff" :foreground "#000000" :inverse-video nil :box nil :strike-through nil :overline nil :underline nil :slant normal :weight normal :height 129 :width normal :family "Bitstream Vera Sans"))))
'(Info-title-1-face ((t (:inherit Info-title-2-face :height 125))))
'(Info-title-2-face ((t (:inherit Info-title-3-face :height 125))))
'(Info-title-3-face ((t (:inherit Info-title-4-face :height 125))))
'(cursor ((t (:background "#04ABFF")))))
I. e. you might try changing "Bitstream Vera Sans" to something else? Or if you have something there, change it to one of the other semantic font names that is installed on your system, and see if it works?
I. e. change the line (if your ~/.emacs even HAS such a line!), save the file, then try to restart emacs.
To find out which fonts you have on your system, I've got no idea... on FC6, in its older KDE version, I can go into the Control Center >> Appearance & Themes >> Fonts screen and the semantic font names there all seem to work in my local emacs.
Hope this helps!