What surprised me the most from Paul Graham's Yahoo article was he was "sitting in my cubicle". I don't see how you could make someone a millionaire, and then put them in a cubicle, and expect them to stick around.
As someone who has been in this situation more than once, a cubicle versus a desk versus an office is not the issue - the issue is, can you motivate people with work they are passionate about and an incentive/compensation plan they feel is fair. Once you have those pieces in place, the work environment usually doesn't matter as much (and to the extent it does, the newly motivated employees will take steps to fix it on their own).