We were a little bit lucky in this regard, because we had some authority in the niche (2 members of our original team had spoken at security conferences internationally for the previous 10 years).

I have lots of thoughts on this though. I think with a low enough burn rate, you can overcome this with a great product, and taking just one bite at a time. ie. one happy customer, then another. Actual customer happiness is so low, that you just have to do a little better to have people talk about you, and over time it compounds nicely.