If you are running Windows 10 Pro, the first thing to check is that the
Start Layout group policy setting is not set under
Administrative Templates\Start Menu and Taskbar. This setting is under both
User Configuration and
The actual problem for me was caused by changing the timezone. Since this was a new install of Windows, and now since the Creators Update Windows does not ask you for the timezone during the install, I had to manually set the proper timezone in the Settings app. In my case, I set the timezone from UTC-8 to UTC-5, so back 3 hours. Due to a possible caching problem with the Windows 10 Start Menu, any changes I made to the Start Menu would not be saved. Whenever
explorer.exe was restarted (from a Windows reboot or through the Task Manager), any changes would be reset.
The solution was simply to wait 3 hours for the time to catch back up to the original time before the timezone change. I verified this by changing the timezone from UTC-8 to UTC-5, verifying that it broke the Start Menu, waiting 2.5 hours, checking that the Start Menu was still broken, waiting another hour (now 3.5 hours), and verifying that the Start Menu was now fixed. I did not do anything else to the computer during this time.
Therefore if your Start Menu is not updating and you recently changed the timezone, just wait for a few hours and it will fix itself.
Edit: As this seems to be fairly popular, it would be nice if someone forwarded this bug to a Microsoft employee :)