The "Start Here" is a text file in the Desktop directory under your home directory: ~/Desktop/starthere.desktop
Contents in mine:
a whole bunch more lines for various locales
If your starthere.desktop doesn't look like that then maybe that's the problem. If it looks ok, try typing start-here:/ in the location bar of Konqueror. Using KDE, I do that and get 3 v-folders: Applications, Preferences, and System Settings. If you don't then maybe some of the files where these are set up are messed up.
I'm not sure where all that is kept and how it differs between Gnome and KDE on Fedora( which I'm using, but in KDE). It might be informative to try logging in as a different user and see if you get the same error.
Don't know if that helps much, but maybe it'll give you a start.