This can be caused by a misconfigured system policy or group policy.

Check the settings for User Configuration / Windows Settings / Folder Redirection / Start Menu.

The default value is %USERPROFILE%\Start Menu.

To fix the problem, use Regedt32 to navigate to:

HKEY_CURRENT_USER/Software/Microsoft/Windows/CurrentVersion/Explorer/User Shell Folders/Start Menu

The Start Menu value name should be a REG_EXPAND_SZ data type, that is ordinarily set to %USERPROFILE%\Start Menu.

The path specified must be reachable when a user logs on.