Conjectures (or intuitions) that turned out wrong in an interesting or useful way The question 
What seemingly innocuous results in mathematics require advanced proofs? prompts me to ask about conjectures or, less formally, beliefs or intuitions, that turned out wrong in interesting or useful ways.
I have several in mind, but will provide just one here now, as an example.
For centuries mathematicians tried to show that Euclid's parallel postulate followed from his others. When Lobachevsky,  Bolyai and Gauss discovered that you could do interesting geometry just as consistent as Euclid when the parallel postulate failed a whole new world was open for exploration.
One example per answer, please. If you want to post several, answer repeatedly.
Related:
Conjectures that have been disproved with extremely large counterexamples?
 A: Perhaps the problem of squaring the circle fits the bill? It is the challenge of constructing a square with the same area as a given circle by using only compass and straightedge (and a finite amount of time), and dates back, in some form, at least to the Babylonians. The solution requires the construction of the number $\sqrt{\pi}$. In 1882, Ferdinand von Lindemann showed that the undertaking is impossible by proving that $\pi$ is transcendental, hence non-constructible. Interestingly, the only property of $\pi$ that comes into play in Lindemann's proof is the good old $e^{i \pi} + 1 = 0$.
A: The intuition that deterministic equations lead to predictable behavior isn't tenable in view of chaos theory. The famous quote from Laplace:

We may regard the present state of the universe as the effect of its
  past and the cause of its future. An intellect which at a certain
  moment would know all forces that set nature in motion, and all
  positions of all items of which nature is composed, if this intellect
  were also vast enough to submit these data to analysis, it would
  embrace in a single formula the movements of the greatest bodies of
  the universe and those of the tiniest atom; for such an intellect
  nothing would be uncertain and the future just like the past would be
  present before its eyes.

Poincaré discovered that with anything less than perfect knowledge (e.g. only knowing the data to finitely many decimal places) this isn't true. In something as simple as the three body problem there are solutions which exhibit sensitive dependence on initial conditions: arbitrarily small changes in initial conditions lead to radically different long-term behavior. If our knowledge of the initial conditions is only out to a certain number of decimal places, then the initial conditions we use will differ by a small amount from the true initial conditions, hence any long-term predictions we will make of the system will be worthless as predictions.
A: From coding theory --
If you want to transmit a message, say 0 or a 1, through a noisy channel, then the natural strategy is to send messages with redundancy. (A noisy channel takes your message and brings it to its destination, though with a chance of scrambling some of its letters.)
For example, suppose I wanted to transmit to you $0$ or $1$ -- $0$ for upvote and $1$ for downvote, say, though this narrative choice is mathematically irrelevant.
Suppose our channel is such that the chance of a single transmitted zero changing to a one is $.1$. If I send you the message $00000$, as long as 3 of the zeros remain zeros, you will be able decode my message by majority voting with a greater probability than if I just sent you a single $0$. 
(Simlrly to hw you cn rd ths?)
The collection $\{00000,11111\}$ is what a code is, and $00000$ is called a codeword.
By continuing this way (for example by sending a million zeros to transmit the message zero), you would be able to drive the probability of a miscommunication as small as you want, however, at the cost of requiring a longer and longer transmission time to send the same message (zero or one).
If you call the rate this ratio ( the number of messages you send ) / (the number of symbols in your message), this naive coding method described lets you make the error small but at the cost of sending the rate to zero.
According to sources I've read (but how historically accurate they are I cannot say), practitioners in the field of communications (e.g. telegraph engineers) thought that this trade off was absolute - if you want to reduce errors, you must drive the rate to zero. 
This is a plausible thing to conjecture after seeing the above example - or anyway you could probably get people (students) to nod along if you told showed them this example and told them this false conclusion confidently. (Conducting such an experiment would be unethical, however.)
However, in 1948 Shannon proved a remarkable theorem saying that this trade-off was not so absolute. (The noisy channel coding theorem.) Indeed, for any channel there is a number called the "capacity" (which in the discrete case can be computed from the probabilistic properties of the channel as an optimization problem over probability distributions on a finite set), and as long as you do not try to send at a rate better than this capacity, you can find  ways to encode your messages so that the error becomes arbitrarily small. He also proved that this capacity bound was the best possible.
One catch is that you need to have a lot of messages to send; if you want to send one of two messages over your channel (and then close the channel for business), then you really cannot do better than the naive method above. Shannon's proof is asymptotic, asserting that as the size of the set of possible messages goes to infinity, you can (in principle) find encoding methods that make the error low - morally, you can keep the code words far from each other without using too many extra bits to pad the transmissions against errors, because there is a lot of extra room in higher dimensions.
His proof opened up a huge amount of research into explicit constructions of codes that approach his bound, which has connections to many other topics in mathematics and computer science.
https://en.wikipedia.org/wiki/Noisy-channel_coding_theorem
If you want to learn the precise statement, the book Cover T. M., Thomas J. A., Elements of Information Theory, is excellent.
A: The first thing that came to mind was the proof that a general expression for the roots of a quintic (or higher) doesn't exist (Abel-Ruffini and Galois). People in previous centuries had thought it might be possible, and searched for the solution. The area of maths that Galois sparked was revolutionary.
A: I have recently read some material on the surface tiling problem, and some results looked really interesting. Perhaps one of the most interesting ones is Rice's Pentagonal tiling (although this might not be considered as a counterexample to a conjecture, but anyway...)
But the more relevant problem is Keller's conjecture, which states that

In any tiling of Euclidean space by identical hypercubes there are two cubes that meet face to face. For instance, in any tiling of the plane by identical squares, some two squares must meet edge to edge.

While it seems intuitively obvious in two or three dimensions, and is shown to be true in dimensions at most 6 by Perron (1940). However, for higher dimensions it is false.
A: Kurt Gödels Incompleteness theorems in mathematical logic came as a shock to many mathematicians in a time when formalistic optimism ruled: 
The theorems state that a sufficiently powerful theory always must have statements which are possible to express but impossible to prove / disprove, making mathematics a forever unfinishable "game" or puzzle as any of those unprovable statements can be chosen to be added as an axiom.
A: Maybe not the answer you expected on a mathematical site, but it feels fitting. 
In the 19th century, scientists were convinced that all matter obeys Newtonian laws. The only small problem was a pesky anomaly: all equations predicted that black bodies should glow bright blue, but in reality they don't. 
Max Planck was one of the people who tried to solve it. He tried using the equation 

$E=nhf$ 

with $E$ for the energy, $n$ for any integer, $f$ for the particle's frequency, and $h$ for an arbitrary constant. 

Planck's assumption was not justified by any physical reasoning, but was merely a trick to make the math easier to handle. Later in his calculations Planck planned to remove this restriction by letting the constant $h$ go to zero. [...] 
  Planck discovered that he got the same blue glow as everybody else when $h$ went to zero. However, much to his surprise, if he set $h$ to one particular value, his calcuation matched the experiment exactly (and vindicated the experience of ironworkers everywhere). --- Herbert Nick, "Quantum Reality"

That's how Planck discovered Planck's constant, and as a side effect, quantum physics. 
A: Gödel's completeness theorem: the fact that every tautology in a first-order language can be derived logically with rather simple and intuitive means. It shows that logic can do more than one would naively expect. For me, it was a shock when I learnt it.
If you say it's just my personal shock and as such not subject of the question — well, not really: there is a respectable tradition that implies logic is very limited, though this tradition is not within mathematics; it's within Russian artistic literature, and also within discussions of art in general (“truth and lie are not really dissimilar”, and so on). No contradiction, of course.
A: The idea that the motion of every celestial body must be a perfect circle, and that, when it wasn’t, the way to “save the appearances” was to add epicycles around the cycles, turned out not to be a useful theory.
However!  It turns out that calculating epicycles (in a slightly different way than the Aristoteleans historically did) is equivalent to finding the Fourier transform of a planet's motion, and converting it from the time domain to the frequency domain.
A: As you wanted separate answers for each suggestion, another interesting one is the proof that angle trisection is impossible. People had been searching for a method to trisect an angle for about two thousand years, and the answer came from the most unlikely of places at the time - the relatively arcane area (at the time) of abstract algebra.
A: Here is one, as pertains to:

beliefs or intuitions, that turned out wrong in interesting or useful ways.

Paul Cohen was toying with ideas around a "decision procedure" that could take as its input a mathematical assertion, and create as its output a mathematical proof or refutation. Here are two relevant quotations directly from Cohen:

At the time these ideas were not clearly formulated
  in my mind, but they grew and grew and I thought,
  well, let’s see—if you actually wrote down the
  rules of deduction—why couldn’t you in principle
  get a decision procedure? I had in mind a kind of
  procedure which would gradually reduce statements
  to simpler and simpler statements. I met a few
  logicians at Chicago and told them about my ideas.
  One of them, a graduate student too, said, “You
  certainly can’t get a decision procedure for even
  such a limited class of problems, because that
  would contradict Gödel’s theorem.” He wasn’t too
  sure of the details, so he wasn’t able to convince
  me by his arguments, but he said, “Why don’t you
  read Kleene’s book, Metamathematics?” (Albers &
  Alexanderson, 1990)

As to the relevance of this quotation to the question at hand, this mistaken "belief or intuition" reared its head later on in Cohen's work:

Because of my interest in number theory, however,
  I did become spontaneously interested in the
  idea of finding a decision procedure for certain identities . . . I saw that the first problem would be to develop some kind of formal system and then
  make an inductive analysis of the complexity of
  statements. In a remarkable twist this crude idea was
  to resurface in the method of ‘forcing’ that I invented
  in my proof of the independence of the continuum
  hypothesis. (Albers & Alexanderson, 1990)

Specifically, one could speculate that it was Cohen's lack of familiarity with mathematical logic (i.e., the incompleteness theorems) that allowed him to form naive beliefs/intuitions which, by his own account, were useful insofar as they reappeared when he developed his approach to forcing. 
The interview from which the above two excerpts are derived is worth a read; as a piece of shameless self-advertising, I included both quotation pulls, along with a fair bit more, in the following paper:

Dickman, B. (2013). Mathematical Creativity, Cohen Forcing, and Evolving Systems: Elements for a Case Study on Paul Cohen. Journal of Mathematics Education at Teachers College, 4(2). Link (no pay wall).

A: A big surprise (at least for me) was that one can use linear transformations over simpler scalar fields to investigate more complicated types of numbers. This is what is done in representation theory. 
For example we can build the matrix
$$\left[\begin{array}{cccc}0&0&0&1\\0&0&1&0\\0&1&0&0\\1&0&0&0\end{array}\right]$$
Can be used to represent the permutation $1\to4,2\to3,3\to2,4\to1$. In similar ways one can show any finite groups elements can be represented with some set of permutation matrices.
Another example from an infinite group is the Quaternions which can be represented as a matrix containing only the real numbers $a,b,c,d$:
$$a+b{\bf i}+c{\bf j}+d{\bf k} \rightarrow \left[\begin{array}{rrrr}a&-b&-c&-d\\b&a&-d&c\\c&d&a&-b\\d&-c&b&a\end{array}\right]$$
So we can do linear algebra over matrices containing already known numbers instead of having to program a new calculation machinery for each new type of numbers we invent.
A: Euler, Gauss, Riemann, Lagrange, Poincare and various other eminent mathematicians were horrified by the infinite and deemed it to be something that only some mad philosopher ought to deal with. This view was indeed even heralded among the Greeks, for they thought that the art of mathematics deals only with the certain and the precise, and that surely dealing with something as outrageously paradoxical as the infinite would only result in the destruction of such a steadfast discipline.
Out of such glorious names, one may pick out a saying of Gauss in particular;

I protest against the use of infinite magnitude as something
  completed, which is never permissible in mathematics. Infinity is
  merely a way of speaking, the true meaning being a limit which certain
  ratios approach indefinitely close, while others are permitted to
  increase without restriction. [In a letter to
  Schumacher, 12 July 1831]

The authority of Gauss was rather strong, and for a long time, only finite magnitudes and lines were meddled with. But the great Cantor sought to demolish such traditions. He proved that it was possible to introduce
into mathematics definite and distinct infinitely large numbers and
to define meaningful operations between them. And with that, the whole of mathematics went through a truly remarkable change.
A: The idea of infinitesimal numbers goes back to the ancient Greeks, before being reformulated by Newton and Leibniz.  The lack of rigor in their formulation led to standard analysis, and then the investigation of whether infinitesimals could be part of a rigorous theory led to nonstandard analysis.  A false dawn, then three major theories over the course of millennia!
A: The Hirsch conjecture stood for $50$ years:
Any two vertices of the polytope of $n$ facets
in dimension $d$ can be connected by a path of at most $n−d$ edges.
(This is equivalent to the $d$-step conjecture:
the diameter of a $2d$-facet polytope  is no more than $d$.)
Santos constructed a counterexample to 
the Hirsch conjecture in $d=43$:

Santos, Francisco. "A counterexample to the Hirsch conjecture." 
  Annals of Mathematics, Volume 176, pp. 383-412 (2012).
  arXiv:1006.2814 (2010). (arXiv abs.)
  
            
  


Added. 
The Polynomial Hirsch conjecture
is the subject of a PolyMath project, and remains open.
A: Rejecting the idea that there was no square root of -1 led to the development of the complex numbers, and moving past the idea that there could be only one imaginary unit led to the quaternions.  (You could consider the ancient intuition that the square root of 2 should be a rational number a similar case.)
A: Polya's Conjecture
What is it?
Polya's conjecture states that $50\%$ or more of natural numbers less than any given number $n$ have an odd  number of prime factors. More details on the conjecture can be found here and here.
How is it Interesting or Useful?
It's pretty useful because the size of the smallest counter example is $906,150,257$. This means it serves as a valuable lesson to younglings about why mathematicians have to use proofs instead of empirical verification. This value is amplified by the fact it's a pretty easy idea to explain to even elementary school students.
A: The example of Newtonian physics is given but here is another example, from physics, that made me shocked when I learned:
Schrödinger Wave Function is a mathematical description of the quantum state of a system and it gives most of the properties of a physical matters with respect to time and space; therefore it is one of the building blocks of quantum mechanics. It is represented by $\psi$ and time dependent Schrödinger Wave Equation is $$ iħ\frac{\partial}{\partial t}\psi(r,t) = \hat{H}\psi(r,t)$$
where $i$ is the imaginary unit, $ħ$ is called reduced Planck constant, that is $\frac{h}{2\pi}$, $r$ is the position vector, $t$ is the time, and $\hat H$ is the Hamiltonian operator. After Schrödinger's Wave Equation was published 1926, there were many comments and interpretations of the Wave Function $\psi$ from some of the most renowned scientists of that time:


*

*According to Max Born and Heisenberg, there is no physical quantity meeting the Wave Function $\psi$. To them, it is just a probability wave (for more information, https://en.wikipedia.org/wiki/Probability_amplitude).

*According to Schrödinger himself, $\psi$ is counterpart of the waves that exists in reality (By that I mean they are not like probability waves or waves that should exist in theory. They already exist and $\psi$ is one representation) (for more information, https://en.wikipedia.org/wiki/Schr%C3%B6dinger_equation and https://en.wikipedia.org/wiki/Wave_function).
Here comes the most interesting part according to me:


*

*According to Einstein, Rosen and Podolsky, Schrödinger Wave Function does not provide a complete description of physical reality, therefore it is an incomplete theory (for more information, https://en.wikipedia.org/wiki/EPR_paradox). Even though this interpretation leads them to create EPR paradox (but later it is resolved) which takes part in development of quantum mechanics, their intuitions about quantum mechanics were proven wrong by the following event:


(Before that, as you know, without axioms mathematics would not have solid foundations)


*

*Paul Dirac and John von Neumann gave a mathematical formulation of quantum mechanics in terms of operators on a Hilbert space with Dirac-von Neumann axioms. After that, Schrödinger Wave Equations and Wave Function were mathematically proven and this showed that quantum mechanics is complete (at least mathematically) (for more information, https://en.wikipedia.org/wiki/Mathematical_formulation_of_quantum_mechanics).


To sum up, although all of these renowned scientists have a role in development of quantum mechanics and they supported their intuitions with solid physical phenomena (thought experiments are included when their knowledge about physics is thought), they were not completely right when we see their arguments. To me, this is one of the best examples that show how physics (and mathematics, indeed) is developed by accumulation of incomplete (or even partially false) ideas.
