I missed your original message, but going by the subject... I had a few icons missing (notably Rhythmbox, I forget the others) from my GNOME Applications menu. It turns out this is because I had some files in ~/.local/applications that were hiding my icons. If this is your problem, try fixing or removing any files in ~/.local/applications.