Just to confirm, I had this problem - all icons in the desktop and through Nautilus were missing, changing the theme corrected the problem. Thanks for the advice! -- scoultas