Reread this and imagine it's a code contest. Less subjective maybe, but would you want to build for someone with such a vague demand? "I need it to do, err, I don't know. Can't quite put my finger on it."
but it's not a code contest. Design is totally different.
No it's not. Good design is about solving a problem, and you can't do that without understanding the problem. Just like you (and me! because I'm a compiler programmer, at heart) can't really solve a problem we don't understand. You can't come to me and tell me to build you a mobile app for your business, just because I know the ARM architecture... I need to understand your business first.
You know what's funny? We use the word "design" for software, and you wouldn't think that you could run a contest to pick the design of a software system. But nevertheless you think someone can design his communication strategy & brand identity by a contest, without spending the time to write down the requirements first.
To the OP: my advice is, just don't bother with a contest or a logo. Find someone (a friend) who is good at typography, and ask him to typeset the word "Tarsnap" for you in a way that looks good on that banner. Just use that as a logo, until you have the time & resources to hire someone to do a proper brand identity for you (because that's what you are asking for here, not just a logo)
By holding the contest, he can get dozens of submissions. They may not be well-designed, but he can use the best theme from the designs submitted to hire a top-notch designer and polish it up, if need be.