For example, "John was asked to solve a complex challenge."
I find this to read very awkwardly, as if someone told me they solved a banana. Is this a case of verb-noun mismatch?
So long as the noun is something solvable, this would be a valid construction. Thus puzzles, Rubik's cubes and equations are all nouns which can be the object of the verb "to solve". So if the challenge was a puzzle, it could be solved. If the challenge was, however, physical in nature, it would be more natural to say that the challenge was completed. The answer to your question is thus "it depends on the nature of the challenge in question - if the challenge can be said to have a solution, it is acceptable to use the verb 'solve'".