its not just the start menu its the EVERYTHING that's changed all at once and requiring users to make a fundamental change in the way they use tools is going to meet resistance.
Changes like this should be introduced gradually, not because we're a bunch of whining sniveling children but because require a large adjustment all at once leads to user frustration and poor efficiency during the transition time.
That was my experience with Windows 8. I was very frustrated with losing the start menu, because, over time, I had customised mine to be able to do almost everything through it. All of a sudden I couldn't find anything, and couldn't understand what principles (if any) were behind how it was laid out. I had to google for how to shutdown the computer, how to close a Metro screen, how to run a DOS command, etc...etc...
I had expected it would take me about a week to master Win8, and be then I'd like it. After a month, I was still cursing it.
I considered gettting a Start menu replacement, but before I did I started to "get" the Metro interface, and realized that I actually like having two layers for mywork, ie. that I can leave some things on the top (Metro) and leave the desktop uncluttered. After a while I had also put all my regularly used programs into the taskbar.
So, it was a vicious learning curve which I would have abandoned if I weren't locked in, but now I'm happy with the Win8 UI, and would opt-out of the Start menu, if it were available.
If that's the experiece of a tech-savvy, Windows veteran, I can only guess at how less technical people have handled the transition. I expect that many of them still don't know how to close a Metro window (you "grab" the top with the mouse, and pull it down, btw)