The problem with the start menu going away isn’t that it was a great UI in the first place. No, it wasn’t even all that good.
The problem with it going away is that it got thrown away, and then replaced with something even worse.
To make one of those unavoidable car analogies, it was like replacing a 1986 Chrysler LeBaron with a 1978 Chevy Pinto. Yes, both are crappy, but the Pinto is so much crappier than the Chrysler is why people complained, not because the Start Menu was the end-all and be-all of good UI design.