The problem -- if it is one -- is certainly not limited to the Win 8 Start menu. There are plenty of interfaces where pressing a button, or some similar action, pops up a new full-screen or nearly full-screen UI element that looks & works differently from what was there before.
I wonder whether any research has been done on whether this makes any significant number of users forget what they were doing. If not, I think such research would be worthwhile.
Normal task switching is near instantaneous, but full screen apps add about 0.3 seconds of animation to their switch. It's enough to break my concentration, so I end up rarely using full screen even though I prefer it for most apps.
And now they killed quick launch bar, so I have to look for a task button and scroll-click on it [inconveniently] to start another window. I’m using 7taskbar+ or something like that to return back to 2000s.
You can hide the search box and still use that functionality by pressing windows and just typing the term.
Saves space in the dock
In Windows 95 and NT 4 it was indeed horrible and there were as many complaints about the original start menu as there was the full-screen one. This was mostly handled starting with Windows 2000 by having the first few icons in the menu be frequently used items. The things you use 90% of the time were no more than two clicks away. (One if you pin it to the task bar.)
Search was added in Vista but was unreliable because the word matching wasn't predictable. Today I was having to use regedit on Windows 7 and the icon wouldn't be shown until I typed the 'd'. Windows 10 improved a lot, though I still am befuddled why it decides to show or not show certain things.
Also, it's further confused by their being two searches. The box you see when you press the Windows key or icon isn't the same as the Cortana bar. Add to that that opening a link to a website from there will always send you to Edge. It's easy to be skeptical about what Microsoft will do with search in the future. How will you feel if in three years they do away with the search box that you've become accustomed to?
The traditional hierarchical tree that showed you what was available, by grouping them into narrower and narrower groups, is awesome if you don't know what you are looking for, as exploring is neigh impossible.
Guessing search terms in wider and wider circles is very unsatisfying.