I think more companies should take the Valve (was it Valve?) approach to intuitive UI design.
Take a person with little experience with computers (and most certainly no experience with the product you are developing), sit them down, start the program, and watch them for an hour or so. The devs are not allowed to talk to the tester until the time period is up.
Preferably, you would want to have more than one person per cycle, to mitigate that "intuitive to person A but not person B" effect.
You could possibly get a few other audiences as well, like those who are familiar with computers but not the genre of game, and those who are familiar with the genre of game but not this game exactly, and see how the responses differ as you get closer to the target audience.
Of course, this does rely on having some good "sufficiently uninformed" testers around, which is not always easy, or cheap.