My biggest (actually, only real) issue with my Windows 8.1 installation is with the type-to-search feature not being good enough.
Let's say I want to start visual studio. You'd expect Windows Key + "Vis" + autocomplete to work. Nope. Visual Studio uses "VS 2012" as the shortcut name. Visual Studio is the name of the start menu folder, but the shortcuts themselves have names that are very unclear and unsearchable on their own.
This is not limited to Visual Studio, lots of software (old and new) does this.
Similarly, a lot of older software seems to simply have "uninstall" as a shortcut, without the name of the program. So typing "uninstall" will give me dozens of icons without any context about what program it belongs to. If I want to uninstall a program (without going through "Add or Remove Programs") I have to manually look up the start menu folder and click on the uninstall icon.
The fix is easy enough: include start menu folders in the searching. First as labels giving context to search results. Second as search queries that can be done directly, or (ideally but more difficult to implement) as contextual information aiding the search. So something like "[program name] uninstall" resulting in the program name folder, the contents of which are then filtered to the shortcut with "uninstall" in the name.