*I will preface this with the statement that I came into tech from running a creative agency - so take this for whatever its worth.
I think that image is just as important as tech, and those that can put the two together will have a much easier time finding users/customers, and partners.
The cost to have your brand built-out, by a creative agency actually worth paying is in the $15,000-$25,000 range. The math behind that is basically: good agencies work for about $200 per hour (per person) and typically a job like a brand buildout will require 3 people, for about a week. That is 120 hours of work @ $200 per hour, or about $25k. I can tell from experience that you can find deals - sometimes; but I would go into with my eyes wide open, and look into groups that work at that level/rate.
Edit: I did not answer your actual question. The answer is, as soon as you can put together the money to do it.