The split up of apps and settings in the start menu search is up there with the removal of aero in terms of Win8 changes that frustrate me greatly.
Luckily I discovered a shortcut that lets you search immediately through settings. Press Win+W at any time and start typing. Now if only my OTHER frustration had a real, working workaround.