Gnome actually uses Nautilus to draw the desktop (icons and all), and therefore if there's a prob with the desktop icons, that's the source. In earlier versions you could disable Nautilus from drawing itself to the desktop, in favor of just using the root window, but last time I checked this is more difficult to do (as anything designated "advanced" is effectively hidden from the user). Personally, I'd recommend KDE. There's more eye candy, and all of the configuration is at your finger tips, but still very intuitive and fun to use.
Anyhow, try looking in your ~/. dirs, as well as ~/Desktop. Other than that, I wouldn't know, as I rarely use Gnome ever anymore.