Long-lasting errors in computer science This is my first question on the cstheory stack, so don't be too rude if I'm violating etiquette somehow ) 

As we know, in mathematics even famous mathematicians, superstars and geniuses are doing serious mistakes time to time. For example, both 4-color theorem and Fermat theorem provide us dramatic cases of how even brightest minds can be deluded. It even can take years to prove the incorrectness of some falsy proofs.

My question is - can you provide some outstanding examples of such mistakes in computer science? I don't know, something like "Dr. X has proved in 1972 that it is impossible to do Y in less than O(log n) time, but in  1995 it turned out that he actually was wrong".
An infamous example in computational geometry is the incorrect proof of the Zone Theorem for hyperplane arrangements published by Edelsbrunner, O'Rourke, and Seidel [FOCS 1983, SICOMP 1986].  The proof also appears in Edelsbrunner's 1987 computational geometry textbook.


  Zone Theorem: In any arrangement of $n$ hyperplanes in $\mathbb{R}^d$, the total complexity of all cells intersecting any hyperplane is $O(n^{d-1})$.


The Zone Theorem is a key step in the proof that the standard recursive incremental algorithm to build an arrangement of $n$ hyperplanes in $\mathbb{R}^d$ runs in $O(n^d)$ time.

In 1990, Raimund Seidel discovered that the published proof was incorrect, after being challenged on a subtle technical point by a student in his computational geometry class.  Meanwhile, a huge literature on hyperplane/halfspace/simplex/semialgebraic range searching had been developed, all of which relied on the $O(n^d)$ construction time for arrangements, which in turn relied on the Zone Theorem.  (None of those authors noticed the bug.  Raimund had taught the published "proof" in detail for several years before he was challenged.) 

Fortunately, Edelsbrunner, Seidel, and Sharir almost immediately found a correct (and much simpler!) proof of the Zone Theorem [New Results and New Trends in CS 1991, SICOMP 1993].