If you did your System Restore to before Classic Shell was installed, some of its components may no longer be registered. Download the latest version from
www.classicshell.net and install it.
Open Classic Start Menu Settings and make sure "Start automatically for this user" in turned on, on the General Behavior tab.
This should solve your problem but if the menu still does not start automatically, go to C:\Program Files\Classic Shell from File Explorer and right click ClassicStartMenu.exe, click Copy in the context menu. Then browse to C:\Users\<Your user name>\AppData\Roaming\Microsoft\Windows\Start Menu\Programs\Startup folder. Right click an empty area and click Paste shortcut.
Now your Classic Start Menu should start reliably at startup every time.