Unfortunately none of that worked. I did a rebuild on the indexing and nothing changed.
Just to explain the situation again, when I go to the start menu and type (for example) cmd in the search bar, nothing shows up. "No items match your search" is the only thing that shows. This goes for anything program I type into the search bar. There are no updates available for the PC. It is a Windows 7 Pro 32-bit.