Things like "sales of cold medicine" and the like fall under the heading of "syndromic surveillance", and believe me, they've been tried for the better part of a decade without yielding much that's impressive. Which is frustrating, because theoretically they should be amazing, but they just aren't, especially when asked to predict rather than back fit.
The CDC numbers (which are part of ILINet) are pretty decent, and one of the things they do, which hasn't been mentioned here, is they're not trying to find all cases of influenza. They have a network of physicians in all 50 states reporting "Influenza-like Illness". These people then also send samples in for laboratory confirmation of virus type, drug resistance, etc. The numbers are also backwards revised as more data comes in, meaning they improve over the course of the year.
It's a very good system for getting an idea of how "bad" the flu season is - the main problem is that it's slow. The ideal, and what people were hoping from Google Flu Trends (and other systems like it, it's not alone) is "ILINet, but in real time".
[edit: For example, the author of the paper could have compared Google and CDC versus a third data source, like sales of cold medicine. That would have been an interesting comparison, and might have shed some light on which estimates were a better reflection of reality.]