You are correct this is a Nautilus issue - if you have Gnome
However this is the kind of problem that is most difficult to solve, the "happens occasionally" problem
This might help. Start gconf-editor* and search for the Apps->Nautilus->Preferences->Show desktop key. Uncheck and check the checkbox a few times.
*Use gconf-editor in a terminal or a launcher (Alt+F2)
Don't fix it if it ain't broken, don't break it if you can't fix it