I have observed the same issue over the past few months. It's a dealbreaker of a problem: instead of running the application you asked for, more often than not you are directed to the application's website.
I've been able to avoid this problem by replacing the start menu with Classic Start Menu, but that comes with its own set of issues (lag, funky focus interactions, and inability to launch some metro apps). So far, this is the only issue that has me thinking about downgrading.
I've been able to avoid this problem by replacing the start menu with Classic Start Menu, but that comes with its own set of issues (lag, funky focus interactions, and inability to launch some metro apps). So far, this is the only issue that has me thinking about downgrading.