Publishing Valuable but Incremental Result
My interpretation is that the reviewer(s) consider that solving the specific problem is not a particularly significant outcome. Assuming that they are right in this judgement (they may not be), the paper must distinguish itself in other ways.
Maybe the problem/solution is shown to have parallels with some other problem/solution. Maybe the solution is radically different. Or maybe, as in your stated case, the solution is simpler than expected. You must identify which of these is most correct and focus on presenting that as the centerpiece of your work. If the simplicity/elegance is what stands out most, find a way to validate and quantify the simplicity, and use that as the central theme.
If, on the other hand, you are convinced that the solving the problem is an important outcome by itself, then stick with the paper and submit it elsewhere. It is very common that reviewer assessments of relevance/novelty vary widely.
Onto the larger point of incremental improvement being generally given less respect; this is the reality with most products, research output being one. The current model of scholarly publication favours work that will get more attention and generate more downloads/citations. This certainly has demerits, but it is the norm and it's best to live with it. This doesn't necessarily mean you should not pursue this line of enquiry, but you should assess what and why it can be more appealing to the readership. (A demonstrably simple, reproducible solution to a problem of my interest would definitely appeal to me).