The article linked within explains it's not about the cellulose, but about the fact that in one particular case, cheese being labeled "parmesan" was actually other cheeses, with 0% parmesan:
> According to the FDA’s report on Castle, obtained through the Freedom of Information Act, “no parmesan cheese was used to manufacture” the Market Pantry brand 100% grated Parmesan Cheese, sold at Target Corp. stores, and Always Save Grated Parmesan Cheese and Best Choice 100% Grated Parmesan Cheese, sold by Associated Wholesale Grocers Inc., which along with its subsidiaries supplies 3,400 retail stores in 30 states. Instead, there was a mixture of Swiss, mozzarella, white cheddar and cellulose, according to the FDA.
That's genuine mislabeling. But it shouldn't be confused with the normal practice of adding cellulose for anti-clumping -- which is what the headline is implying is the scandal.