Examples of when a "new way of thinking" led to a solution I was reading William Thurston's On Proof and Progress in Mathematics in which he discusses the value of the different ways people think about the same mathematical structure. He claims that many mathematical solutions are the result of different ways of thinking about the same underlying mathematics.
What are some examples of problems that seem very difficult, but yield to a new way of thinking about the relevant structures? 
Answers should include a description of the problem, the “way of thinking”, and the rigorous solution.
 A: The probabilistic method has been successfully used for proving the existence of mathematical objects non constructively, by proving that the probability of choosing an object in that class is not zero.
A: Cohen's discovery of forcing fits the bill, in my opinion.
This one is definitely more technical than may be ideal, but I think it's still cool and interesting. I'm going to avoid a bunch of subtleties, for the sake of readability by a more general audience. Let me know if there is any point you'd like me to elaborate on!
The problem
Go right back to when modern set theory began: the distinction between countable and uncountable sets. After discovering that the real numbers are uncountable, Cantor asked the obvious follow-up question: what, if anything, is in between?
There are two obvious possibilities for the size (cardinality) of a set $X$ of reals: it could be "small" - that is, countable or finite - or it could be as large as possible, that is, of the same cardinality as $\mathbb{R}$ itself. Cantor asked whether there was a third option. That is:

Is there a set of real numbers which is uncountable, but has cardinality $<\vert\mathbb{R}\vert$?

The conjecture that the answer is "no" is the continuum hypothesis.
The background
Time to spoil the punchline: together, Godel and Cohen showed that the continuum hypothesis cannot be decided from the usual axioms of set theory. (Whether this constitutes a complete answer is a topic of debate, but let's stop here for now.) Specifically, Godel showed that ZFC cannot disprove CH, and Cohen showed that ZFC cannot prove CH (that is, assuming that ZFC is consistent - otherwise of course it can do both!). Both parts were revolutionary, but Cohen's specifically involves a complete change of perspective.
Before we can see why Cohen's solution was so revolutionary, we need to say a bit about two things: (i) how proving a consistency result happens, and (ii) how Godel did his half.
How does one prove consistency? By Godel's completeness theorem - no, that's not a typo - consistency is the same as having a model. That is:

To show that "ZFC can't disprove $\varphi$ if ZFC is consistent," it's enough to show how to build a model of ZFC+$\varphi$ from a model of ZFC.

Both Godel and Cohen, therefore, were faced with the question: how do we build models of ZFC?
Godel addressed this problem by discovering a canonical model construction: he showed that any model $M$ of ZFC has a submodel, denoted "$L^M$," of sets which are "nicely definable" within $M$ in a certain way (called "constructible"). This substructure turns out to have lots of "guaranteed" properties, regardless of how precisely $M$ looks; in particular, Godel showed that $L^M$ satisfies CH even if $M$ itself doesn't.
This approach has two fundamental limitations:

*

*The new model we build from the old one is smaller: it's a submodel of what we start with. This runs into a huge mathematical problem: by Godel's work we can show that there is a model of ZFC with no submodel where CH fails (interestingly, this was first observed by Cohen!). So nothing like Godel's construction can prove the consistency of the failure of CH with ZFC.

(Quick historical note: there were techniques for building bigger models from smaller ones, like ultraproducts, but for various reasons these were useless for this problem.)

*

*More insidiously, the new model we build from the old one is specifically described. In going from $M$ to $L^M$ there's no freedom: $L^M$ is completely determined from $M$.

So now, here's what Cohen did:
The solution
Roughly speaking, the idea behind Cohen's approach was the following: given a model $M$ of ZFC, we'll add a "random" object $G$ to $M$ to get a bigger model $M[G]$. By choosing the right notion of "random," this will let us construct models with desired properties.
OK, all the set theorists just cringed. "Random" here is actually an unfortunately loaded word, and in fact "generic" is the term we should be using: the right analogy here is with category rather than measure. However, randomness is a more broadly understood concept, so I'm sticking with that word here. Also, it's not totally wrong either.
An analogy here is often made with the idea of adjoining a new element to a field - e.g. the passage from $\mathbb{R}$ to $\mathbb{C}$ - but such a construction is again "canonical." What Cohen observed was that we can actually get mileage out of deliberately not trying to control the model-building process too much! Remember that "random" is not the same as "arbitrary." The idea that randomness provides structure is of course a very old one in mathematics, but nothing like it had ever occurred within set theory.
The idea of thinking about random sets, and by extension random models, was completely new to set theory. (It arguably was foreshadowed by finite extension and priority arguments in computability theory, but a lot of the relevant complexity rests in how it engages set theory, so that's really dodging the point.) Cohen discovered a way to talk about "notions of randomness" over a model $M$ in terms of partial orders in $M$: every partial order generates a notion of "random extension." Cohen showed how the theory of the corresponding extension is determined by the combinatorial properties of the partial order, and so reduced the task of building a model of ZFC + not CH to the task of building a partial order with certain properties - and this last bit turns out to be incredibly easy.
This is called forcing. Its fundamental novelty can be seen not just in the vast array of open problems it annihilated, but also in the speed with which it was absorbed and transformed by the broader logic community: it really was a couple key paradigm shifts (I've really only focused on part of it above), which once grasped yielded an immediately-usable technique. Too many people were involved too quickly to describe in a single sentence, but amongst the key players were Feferman, Levy, Scott, and Solovay.

If you're interested, you can find more of the history of forcing in Moore's article or Cohen's recollection.
A: An example is Cantor's proof of the existence of transcendental numbers. When he proved it, Liouville had already proved that the statement holds, by providing a way of constructing such numbers. Cantor proved it an a basically different way: by proving that there are more complex numbers than algebraic numbers and thereby proving that the set of non-algebraic numbers (that is, the transcendental ones) is not empty.
