When have we found better bounds for known algorithms? Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - obviously that's happened! But better analysis leading to a better bound on an existing algorithm

I thought matrix multiplication was an example of this, but I have talked myself out of it (perhaps incorrectly!) after trying to understand Coppersmith–Winograd and its friends better.
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).