After I upgraded from 0.30 to 0.50 I also had problem with missing icons etc. on some of my computers running Debian unstable. Today I discovered a folder called .local in my home folder that, among other things, had some mime-related data in it. After I deleted the .local folder I got the correct icons back in nautilus again.
I'm now using 0.51-3 (i386) and everything seems to be back to normal. Maybe this is a solution that will help others that are having the same problem. /Mikael (This is a repost from an other mail account - I think that my first email disappeared into cyber space)
