Trade on #bitcoin-otc, set up an OTC account, and post lots in the forums. Basically, the two components of building up trust are establishing relationships (through trading and discussions here), and time (which you can't really get around). The longer you are on here talking and letting people learn about you, the more developed your trust and reputation (whether that's a good or a bad reputation). Meet some people, make some friends, and establish some networks. Also LinkedIn can help somewhat.
Good advice. Thanks for telling me about #bitcoin-otc.