I don't like that explanation, because my understanding has always been that the toilet is only responsible to get the waste into the main, and the carry distance is not very long. It is other water in the line, from sinks and tubs, that over time move the waste down the line. That was also probably a 3.5 gallon toilet, and if you put in a 1.6 you could expect more problems.
I would suggest that this might be time to get a camera inspection done. There may be a problem in the pipes that on one is aware of.