It is ironic that you accuse me of "unwarranted conclusions". I've been customizing and modifying PostgreSQL internals for almost two decades, I know how to read the source. You aren't as familiar with PostgreSQL as you think you are.
This wasn't my problem, I was asked by a well-known company with many large PG installations and enterprise support contracts to look at the issue because no one else could figure it out. The limitations of the statistics collector are not only evident in the source but they are documented there. There are also deep architectural reasons why you can't trivially modify the statistics collector -- I looked into this option -- to work for larger tables without introducing other serious issues.
If you have a uniform distribution of values, the statistics collector will work fine. In the above case, the values followed a power law distribution which created extreme biases in the statistical model due to necessary restrictions on sampling. Other distributions can have similar effects once you exceed the ability of the statistics collector to acquire a representative sample.