There is one hack that seems to work.

Keeping the app free for its first week on the store. This gets the app in the hands of the right people, the "early adopters". If the app is good, they'll use it and recommended it to friends long after the promotion week is over.

People are not afraid to pay when the trial was confirmed as a success by their friend (who is an iPhone genius).