I can think of three approaches that each have their advocates: the classical, the opportunistic and the lean.
The classical approach focuses on the market rather than the solution. How widespread is the problem? What are the present solutions, how are they positioned and what's their market share? Now, where are the gaps? Now choose the best opportunity, and go for it.
That approach is most commonly seen from larger companies. So the simplest answer to the question, "why would anyone buy this non-existent solution?" is, I already know and trust the company, so why wouldn't I? They know what they're doing, and I want what they're promising. Not every customer will take that attitude, of course, but the subset who do get early value and help to make the new product a success.
The opportunistic approach often comes out of consultants - individuals and small firms. They spot an opportunity because they see similar issues cropping up with a number of clients, and most likely have developed ad hoc answers to the problem. Reflecting on the experience, abstracting away some of the details and coming up with a killer solution built on the experience they've built up defines the opportunity in a bottom-up way (versus the top-down classical approach).
The early adopters and sponsors for the product are the exact same people who bought help at a day-rate. These are well-formed relationships, where there's trust and personal connection.
If those were top-down and bottom-up, the lean approach is a kind of Brownian motion. Here the objective is to distil the insights, however gained, into something as simple and quick to develop as possible, and that will be iterated - the famous Minimum Viable Product or MVP.
You could say it's a cheat for me to include that here at all. After all, typically you're selling something you've built, not pre-selling something you've started work on.
I'd argue, though, that as MVP is as much about the process as the product, it's a valid development route, to be weighed up against the others. For me it makes most sense when the time and effort to define and code the MVP is comparable to the time it would take to pre-sell the full product idea you have in mind. And the customers for the early product are highly likely to be responding to the value of the core feature(s) - which is arguably the best way of validating the general market.
I think all three approaches have their merits. They're not all viable in all areas of development or for all startups, but I'd certainly advise anyone thinking about product opportunities to sketch out how each of the three might work for them.
