Whether or not AppGratis could have seen this coming is debatable, but the product was solid and seemed to have served a genuine need. If the app store would not be broken in many respects then AppGratis would have never been able to carve out the niche that it had.
App curation at the level that AppGratis was doing is really hard work, and you can't blame them for wanting to be compensated for that hard work. So a certain percentage of paid promotion is a fairly obvious step to make the model viable imo.
Their biggest mistake - if you can call it that - was probably to be too good at what they were doing.
In the AppStore no threat to Apple is too big to fail. Better remember that if you are successful with an app you wrote and you are possibly in competition with some portion of the Apple empire.