Bill Gates
I've (seriously) tried reaching him a few times via his foundation (Microsoft refers all queries to them). Never got a response.
Steve Wozniak
He spoke two or three times at VCF West in the pre-VCFed days. It's getting harder to book him post-Jobs, but rest assured, your fellow board members and I know do have occasional contact with him. :)
Nolan Bushnell
Possibly. He was recently in some controversy about sexual harassment though .... we wouldn't want to bring that attention to the organization (his actions are certainly not something to be discussed in any detail on this list, however.)
Paul Allen
We tried, as you know. :) Last time he gave a public speech was several years ago when he donated zillions to a university. LCM director told us to keep our expectations low for ever getting him to speak, however, he IS known to show up to such events just as an attendee! :)
Guy Kawasaki
Cool idea. Maybe for VCF West.