I recommend http://99designs.com/ as a great starting point.

You can run a design contest for a small amount of money, and you'll get a FAR broader range of options than with just one small designer.

You have the option to only pay if you're actually satisfied with one of the entries, so the risk is essentially nothing (ie: just the $39 entry cost).

Be wary that the quality of entries is somewhat in line with how much you're offering and the quality of your feedback. That said, you should be able to get something really decent for <$1000.

Another option would be to trawl the site and find designers who's work you really like, then offer them something inline with what they'd get in the competition environment (but with guaranteed payment).

Cheers!