Windows 7 Strange "Start Menu" search behaviour

[Ambious]

I have a strange issue I could not find online.
When I type anything in the searchbox in "Start Menu", all I get is a strange empty icon which doesn't do anything.
If for example I type in "CMD" it'll show an item called "Programs"
If I type anything that would be found in a document, it shows an item called "Documents" (obviously names of folders or libraries, but they're not clickable).

It should be mentioned that searching in the Windows Exporer window itself works just fine, it's just the start menu search that won't work.

I've tried un/re-installing Windows Search, I've tried the Search and Indexing troubleshooter, and even tried SFC.
Attached is an example of what appears.

 

[reghakr]

Right-click on the Start button and check the two boxes for privacy.

 

[Ambious]

Thanks for replying.
They're checked, and I've already tried un-rechecking them.
Any more ideas?

 

[Mitchell_A]

This has happened to me several times in the past using the beta.. Wish I could remember how I fixed it.
Will post back if my brain comes across it.

 

[reghakr]

I tried a registry hack, but it did not work either, sorry.

 

[Ambious]

Fount this solution elsewhere, and it solved it! give it a try:

1. Open "Regedit"
2. Navigate to: HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\FolderTypes\{ef87b4cb-f2ce-4785-8658-4ca6c63e38c6}\TopViews\{00000000-0000-0000-0000-000000000000}
3. Modify the "GroupBy" and change it's value to "System.StartMenu.Group"
4. Log off / Log on

I'd like to thank everyone who tried to help, cheers!