When have we found better bounds for known algorithms?
The Union-Find algorithm, which Tarjan1 showed had complexity $n \alpha(n)$, where $\alpha(n)$ is the inverse Ackermann function, had been analyzed previously by several people. According to Wikipedia, it was invented by Galler and Fischer2, but this seems to be incorrect, as they did not have all the components of the algorithm needed to make it run that quickly.

Based on brief scans of the papers, it appears that the algorithm was invented by Hopcroft and Ullman3, who gave an (incorrect) $O(n)$ time bound. Fischer4 then found the mistake in the proof and gave an $O(n \log\log n)$ time bound. Next, Hopcroft and Ullman5 gave an $O(n \log
^*n)$ time bound, after which Tarjan1 found the (optimal) $O(n \alpha(n))$ time bound.

1 R.E. Tarjan, "Efficiency of a good but not linear set union algorithm" (1975). 
2 B.S. Galler and M.J. Fischer, "An improved equivalence algorithm" (1964). 
3 J.E. Hopcroft and J.D. Ullman, "A linear list merging algorithm" (1971).
4 M.J. Fischer, "Efficiency of equivalence algorithms" (1972).
5 J.E. Hopcroft and J.D. Ullman, "Set-merging algorithms" (1973).