Right click on the start menu, go to properties, and check to make sure the two options are checked.
The two options are "Store and display recently opened programs in the Start menu" and "Store and display recently opened items in the Start menu and taskbar"
If that isn't the problem, then I am truly stumped. But hopefully, that will work!