It's the "Nobody thought this was possible" that I found curious. Yes, there is a lot of room between O(n) and O(n^2)! That's why it seems strange that it would be thought impossible.

But I guess it is just that people have been working on it for a long time with no progress, and so the thought was that there must be something especially hard about it. And, well, there is something comforting about round numbers, and so O(n^2) is something special, whereas if the O(n^1.9992) algorithm was known from the start I doubt anybody would have been surprised if O(n^1.9991) was possible.