Well, you could fire up REGEDT32.EXE (NOT regedit.exe) and go to this location in the registry:
HKCU\Software\Microsoft\Windows\CurrentVersion\Explorer\User Shell Folders
Look at the following REG_EXPAND_SZ Value Names to see if they show the corresponding appropriate entries:
Programs: %USERPROFILE%\Start Menu\Programs
Start Menu: %USERPROFILE%\Start Menu
and also check these to be sure:
Desktop: %USERPROFILE%\Desktop
NetHood: %USERPROFILE%\NetHood
Startup: %USERPROFILE%\Start Menu\Programs\Startup
If you see evidence of corruption, try editing the values. (Please note that I typed these exactly as they are listed in my registry.)
I have seen corruption in these values cause visual and behavioral aberrations in the Start Menu. Hope this helps.
BTW, are you using any sort of desktop control utility (Norton, Window Blinds, any other such stuff)?
Regards,
Jim