LOL, nobody used? With all due respect I think you need to speak for yourself on this one.
For myself, and everyone enrolled into the Microsoft Customer Experience Program.
"We'd seen the trend in Windows 7," said Chaitanya Sareen, principal program manager at Microsoft, referring to the telemetry gathered by the Microsoft Customer Experience Improvement Program. "When we evolved the taskbar we saw awesome adoption of pinning [applications] on the taskbar. We are seeing people pin like crazy. And so we saw the Start menu usage dramatically dropping, and that gave us an option. We're saying 'look, Start menu usage is dropping, what can we do about it? What can we do with the Start menu to revive it, to give it some new identity, give it some new power?'"
The fact is that practically nobody used the heirarchy menu ("classic menu") part of the start menu. Sure, people used the front part of the start menu, but that's just a collection of fixed buttons (control panel, my documents, shutdown etc) and a random selection of your most used apps.
In Windows8 your most used apps appear in your start screen, and you get more than 7 of them at a time. Most of the complaints are that the other buttons aren't there, but they are, they're just less easy to find.
The problem isn't that Microsoft changed or killed the start menu. It's that they don't make it clear to customers where the buttons have moved to. It really isn't obvious to new users how to turn off the machine, how to get back to the start screen or what the hell the charms bar is or how to get to it, and that's really the problem with Windows8.
So I stand by my assertion: The start menu was a badly collected assortment of randomly changing crap that people didn't use because they were busy pinning the apps they wanted or using search or desktop shortcuts for the other apps. Practically nobody used the dumping ground of the heirarchy and few people used the small number of ever-shifting randomly selected apps on the front screen.
"Killing the start menu" is really interface nostalgia and annoyance at not being told where the fixed buttons (like control panel) moved to inside the start screen.