It seems that some icons got removed from the gnome-icon-theme recently which has caused both problems and some debate. To me there are two issues here. The first is that I think we should start seeing our collection of icons as part of our ABI stability promise. Removing and changing icons names at regular intervals have been the norm for some time now, and as someone who has worked on maintaining themes its been a pain. Application developers and users also have a right to be upset if icons they IMHO rightly could expect to be there suddenly are gone and their applications breaks due to it.
The issue of wether we should have those icons displayed in Nautilus is another separate issue. I don’t have any strong feelings on it, but I think it would have been a better approach to at least add an option of getting those textual descriptions back through a gconf key enabling emblems. So that the people who wanted to keep textual descriptions could do so by enabling one gconf key and emblems would appear where before ‘hardcoded’ images where used. That solution would also allow for a more i18n friendly setup.