Gowers is particularly interested in cases in which a "proof of a statement that was widely believed to be true and was true gave us much more than just a certificate of truth." Reading through the answers, I am struck by a recurring theme. There are many cases where

• something seemed impossible;
• it was impossible;
• a lot of people didn't see the point of proving impossibility;
• the search for an impossibility proof led to the discovery of structures that arguably would not have been discovered otherwise.

Just to list a few examples explicitly:

• It seemed impossible to prove the parallel postulate from the other axioms. The proof of impossibility led directly to non-Euclidean geometries.
• It seemed impossible to "square the circle." The rigorous proof (Lindemann–Weierstrass) forms the foundation of modern transcendental number theory.
• It seemed impossible to solve all polynomial equations using radicals. Rigorous investigation of this impossibility led to what we now call Galois theory.
• (Daniel Moscovich's answer) It seemed impossible to unknot a trefoil. The search for a rigorous proof led to the discovery of all kinds of knot invariants. More generally, topology and geometry are rife with examples of "obviously inequivalent" structures, and the search for rigorous proofs has uncovered all kinds of important invariants.
• It seemed impossible to write down a procedure that would mechanically determine the truth or falsity of an arbitrary mathematical question. The rigorous proofs (incompleteness/undecidability) revealed fundamental limits to human knowledge.

In some cases, you could perhaps quibble with my claim that most if not all people thought these things were impossible, or that people didn't see the point of trying to prove impossibility. In this regard, let me mention the article Why was Wantzel overlooked for a century? The changing importance of an impossibility result by Jesper Lützen. Lützen persuasively argues that Wantzel's proofs of the impossibility of trisecting the angle and duplicating the cube were all but ignored because people just weren't that interested in an impossibility proof of something that everybody already believed, or suspected, was impossible. So even mathematicians are not immune to the tendency to undervalue negative results.