My company was B2B, so it might be different for us then you. However, I'll still spell out what worked for us.
1. Tradeshows. We went to industry tradeshows, and our sales guys really worked the shows. We didn't know anyone in the industry, either. They worked the shows, really got out there to know the people, and worked the people covering the shows (magazines, photographers, etc). Basically, it was all about networking.
2. Advertising in print got us coverage. We bought ad space which came with a write up in the mag and online. Is good because it gave us presence.
3. Presence is important. We'd go to trade shows all over the place, and really mingle. Tradeshows seemed to do well, and was the place for face to face meetings.
4. Incentives to get word of mouth advertising. We would pay commissions to clients who would bring in other people. It wasn't merely a link to click on. Rather, it was direct referrals. "Hey, here's a guy who could use your services..." and we'd give him a fair cut.
But really, presence was the big thing. Being out there, being seen, being apart of the environment was big, and really allowed us to get out there. If you present yourself as a successful company, people assume you are. Obviously you need to back it up when they sign on, but it's getting them to call you back that is important.
Should also stress that most of this was between 2003 and 2006 when we started this and really pushed.