Not just federal fellowships but private and even departmental fellowships as well. Makes for a big surprise tax season when you realize you should have paid estimated taxes.
The government doesn't really know about when you were paid though, so you're unlikely to get hit with penalties if you do forget to pay the estimated tax.
It makes it really fun when you and your spouse are both grad students, and have to deal with that twice.
[1] Okay, not everything, but for the purposes of this discussion, yes.
There is more to "tax status" than whether you must pay income tax. There are payroll taxes, Roth IRA-eligibility, etc.
For more, read Pub 970. It's really quite complicated than whether you pay taxes on the income or not.
Not all graduate stipend (fellowship, etc.) income is taxable, but the part that comes from work (as well as any amount not used for certain purposes, even if it doesn't come from work) done as a condition of the stipend (fellowship, etc.) is taxable:
Suing them is not a good idea, but why not report them? It's not like retribution will come your way and it could be interesting, if not better (as in "less contradictory") for future people in your position.