Windows Metro apps have wrong icon in search UI
If you go to System > Advanced System Settings > Performance >Settings
You should see the option for "Show thumbnails instead of icons."
Click to enable.
A quick reboot and a few minutes, you should see the Windows Store icons reappear. At least this was the fix for me.