In the application log within "Event viewer", Did you get an error (red icon) event 1542 from "User Profile Service" on the reboot just before the start menu died? The text of the event is "Windows cannot load classes registry file. DETAIL - Access is denied."
I do not think that the update is the issue - I think it is coincidence.
I have been doing quite a bit of research on this issue, and think I've got further than anyone else's whose research I've seen, (and only one other has got close). Of course there could be multiple causes of "Your start menu isn't working". My research is centred around that error when the 1542 event mentioned above is logged on each reboot where the Start menu fails. The standard Microsoft fix is to recreate the user account - that works but is highly inconvenient (I've been hit three times in four weeks). The first time, I recreated my profile (which took several hours to get back to where I wanted it). I suspect that your restore point must have reverted the user registry hive in your profile as well.
I traced the issue far back enough to realise that the recovery was really to repair the affected users' Windows profile. More exactly a corrupted registry hive. I figured out what to repair, but unfortunately that turned out to be too complex a fix to post on the Microsoft forum that I broke my research on (which incidentally is still ignored by the Microsoft staff there). My feeling is that releasing the exact details of the fix would be practically impossible to do click-by-click, and would encourage non-technical users to dabble in things that would likely break their system totally, as the instructions could very easily be misinterpreted (*).
What I have not traced yet, is the exact place that the user profile IS being corrupted, and the cause for that corruption (although I do have some suspicions).
The users profile contains parts of the Registry that are custom settings for that user. There are two main registry hives - The User registry have (I'll refer to this as the base user hive below), and the user classes registry hive (the user classes hive).
The base user hive gets loaded first (And is linked to in such a way that t becomes the HKEY_CURRENT_USER predefined key. Very shortly afterwards the user classes hive gets loaded as well. The user classes hive is then linked into a particular place in the base user hive (such that it appears as part of the HKEY_CURRENT_USER tree, a couple of levels deep within that tree). The place where it is linked should NOT be present in the base user hive before the User classes hive gets loaded and linked there.
What I found was that in an affected user profile, registry keys that should be only present when the user classes hive is linked into the base user hive, were present in the base user hive without the user classes hive being loaded. Then when the User classes hive is loading and attempting to link into its place within the base user hive, that place is occupied and the link fails, and the Access Denied error event logged.
The system then continues to limp along without the correct COM classes being present in the user's session, and things fail, the start panel amongst them. Other things limp along and even exacerbate the issue by creating more keys within the base user hive where the user classes hive should be.
What I think is happing is that there is a race condition taking advantage of the brief moment in user logon between the base user hive loading and the user classes hive being loaded (and linked into its normal place within the base hive). In that instant something (I suspect some inbuilt modern apps) tries to reference some keys from user classes hive, but it is not (yet) there, and instead some keys are created within the base user hive where the User classes hive should be. Shortly afterwards, the User classes hive tries to load but cannot as it's place is taken. My feeling is that the opportunity of the race condition needs to be resolved, or the errant processes prevented from loading until the user classes hive is successfully loaded - something that only MS can arrange.
Alternatively, something similar could be occurring when a user logs out (Between the user classes hive unloading and the base user hive unloading). In this scenario, the profile is corrupted on logout/shutdown, and the error first occurs the next logon of that user.
I've also considered a couple of other initial failure (initial corruption) modes that I consider less likely.
* The reason for my caution is that my "repair" involves removing a particular registry key. Unfortunately, there are some subkeys that are difficult to remove due to permissions and several other places were similarly named keys exist (and which would totally break the system if THEY were erroneously removed). another issue is determining whether the key is present as part of the real user classes hive or erroneously in the base hive could if not done correctly cause a healthy classes hive to be deleted.)