Compare this with the question: what makes something heavy? If someone can eventually, in a small amount of time, lift it, is it no longer heavy?
Obviously some people can lift heavier things than others. The key word is heavier. There may not be an absolute property of heaviness, but there is certainly a relative one, which corresponds more or less to how hard it is to lift or move something. (Sheer size can make light things difficult to lift or move as well, of course.)
The same goes for complexity. The entire discipline of theoretical computer science could be said to be concerned with classifying, or reducing, the complexity of problems according to how much work it takes to solve examples of those problems (such as adding two n digit numbers, computing some digit of pi, and so forth). Whether a problem is "hard" depends on what resources the person or machine computing it has: just as a body-builder finds it easier to move a heavy weight than an average person, so a machine which has a lot of scratch-space available to it can more easily solve some problems than others. (Indeed, this is why most people tend to work out problems on paper, or these days with computers, rather than just relying on the organic memory that they have.)
Of course, sometimes a new way to solve a problem is found, and it reduces how much work a problem is; but the solution itself is sophisticated and not easy to understand without study. This is another way in which complexity can be measured: not by how hard it is to find a solution, but how complicated the procedure to find a solution is.
If you find a fast and simple solution to an old and complex problem, does the problem become less complex? Yes. But it's a qualified yes — depending on remembering the fast technique, which is akin to a body-builder maintaining their fitness once they have developed it (or perhaps a better analogue would be having built some simple machines, involving levers and pulleys, to lift the weight, and then either keeping that machinery in good shape or being able to re-build it). Finding the fast technique may not have been easy, but once done it reduces the significance of the problem as long as it is remembered. This could be described as the entire motivation for education.