"Is this even legal?"
I'm not sure if the DOT has a regulation reguarding the draconian changes to FF programs. There certainly is a transportation contract between the FF Pax and the airline should not depend on if that person paid any money for that contract or not. Usually, there has to be some value for FF miles. Assuming the traditional "coupon from the newspaper" rate of 1/20 of a cent, a sum total of 2000 miles is equal to 1 USD so any DOT regulation should apply across the board, FF pax or not.
My 2 cents on the subject. FF miles are becoming more worthless every day. Most go unredeemed (78% is the consensus number) and the rampant inflation of mile reward levels ensures that fewer of them are redeemed for flights. I have given up on milage redemption and just decided to use hotel points instead to save money when traveling. I got some nice hotel redemption deals when I was in Europe 3 years ago and they are even better now that USD is pegged where it belongs given our national debt. USD will depreciate even more now that Fannie Mae/Freddie Mac have the keys to the treasury and allowed unlimited debt loads. Hotel points do have their own inflation but longer trips will necessitate more money to be spent on hotels than the flight there. Also, some hotel chains discount longer stay redemptions (or at least they did the last time I redeemed points). Airlines do not.