Faster horses is still a challenge for solutions that aren't always obvious to people. A vision isn't always the one the customer wants. An obvious solution isn't always the best either. One way I found to help overcome this barrier is testing for symptoms based on assumptions about your new feature set and what you aim to solve:
Cars have wheels. Okay,tell me about your problems with horses and the way they move?
Cars don't need rest. Okay, tell me about your problems with stopping to feed your horses?
Cars are faster. Okay, walk me through a time when you were late to something - why so?
It's easy for a customer to answer all three answers separately, but they'll struggle to put them all together and come up with "car". They've never seen it before. However, you can still validate because their problems are very real. When you have your concept, you can show it, and then validate the final solution.