Could you provide more information about the experiment that you conducted? In real life, users have the option of quitting, and the luxury to do it in private; two things that are very hard to emulate in "experimental" conditions but which greatly affect the outcome. I'm not in any position to judge your experimental techniques, but if you're relying on users actively complaining about things, or worse, telling you what they think they want, you're probably doing it wrong.
It's my opinion that hiding menu items not a great idea for the reasons OP said. In my opinion, coming from someone who's had to use an interface which does this, is that it's borderline obnoxious expecting me to remember where, and that it's necessary, to hover over magical areas to show important controls.
I think having the items be very translucent until hovered provides the best of both worlds. I can see where they are, but are easily ignorable.