If you right click the taskbar and select properties, then under the Start Menu tab, there are two check boxes below Privacy. One for the Start Menu and one for the Start Menu and Taskbar. Are both checked?
While you are there, you may also want to check the customized button and on the bottom it mentions how many programs to display. Make sure they are not set to 0 or some such.