Are you running free trials? Giving potential customers an adequate period of time to evaluate your product can be a good way to get them past some of those early hang-ups, especially if you're there to hold their hand.

Edit: I see in your other comment that it's related to lead gen at trade shows, so see if you can convince customers to use a free trial at a trade show so they can actually see the value (and have invested in the platform with real leads by the time you come knocking with a bill).