I think he will have a hard time getting a qualified designer to take a $500 project seriously. I have no doubt he can get something for $500, but it won't be something he likes.

You are right if you focus solely on designers from countries with a high cost of living. I'm pretty sure the friend who did my little shop's logo(you can see it at http://rightfold.io) could make something that Colin likes for less than 500$.