Carry-on Baggage
As a customer who books your tickets directly on FlyFrontier.com, you will continue to receive a free carry-on bag in the overhead bin. Our customers have told us that finding overhead bin space for carry-on bags has become increasingly difficult, so we will be introducing a fee for carry-on bags for customers who buy Basic fares through third-party websites starting this summer. When these changes have been made, you’ll find more space in the overhead bins for your bags.
Checked Bags
When you buy a Classic or Classic Plus ticket, you will continue to receive two free checked bags, regardless of where you booked. For Basic and Economy tickets booked on or after June 1, 2013 for travel on or after July 11, 2013, the fee to check a first bag will remain $20 when purchased during online check-in at FlyFrontier.com. However, the fee will increase to $25 when purchased at airport check-in. Second bag fees for Economy and Basic bags remain unchanged at $20.
So, to summarize:
1. We are charging people for checking bags.
2. This is leading to people doing more carry-on, which is causing people to complain about lack of carry-on space. So we're going to start charging more folks for carry-on so as to alleviate this problem.
3. We are raising fees on checking bags.
4. GOTO 1
The bottom line, of course, is the bottom line. It's not about customer service. It's about raising more money through fees. More people will be charged for carry-on and for checked bags.
Granted, Frontier is not alone in this. But they're being insultingly disingenuous by couching it in terms of taking care of their customers. Unless "customers" means "folks who buy more expensive tickets."

Hell, one of the reasons that I usually pay for the upgrade on Frontier is to get in Zone 2 and still have room for my bag once we get aboard. It gets a little ridiculous otherwise.
And as long as demand remains high, and as long as most airlines charge the fees, the fees will continue.
It would be interesting to see what would happen if the Federal Government (who I've heard is having revenue problems of its own) were to tell the airlines that it would no longer book flights on any airline that charged baggage fees.
Baggage fees of $20 seem pretty reasonable to me. People with large bags should pay more. On a $400 ticket, my 20 pound bag travels for half the price per pound that I do. Charging a fee also encourages people to travel light, saving on fuel, so I suspect this is good for the environment.
Well, there's definitely a fuel impact. But bag quantity per se is a poor proxy for weight. And the problem is that, as things presently stand, even if you cut the travel quantity down to a carry-on bag (which, depending on the setting, means max three days of duds), you're still being charged.
"bag quantity per se is a poor proxy for weight" Meh. I think most airlines do charge more for exceptionally heavy bags, and bag quantity is not a terrible proxy for weight. Would people actually complain less if the fee was $0.001 per pound*mile (or something) that more accurately reflected costs / environmental impact. I'd be shocked if that was the case. (Also, I'm betting that a lot of the costs of handling bags are per-bag as well, to manage the conveyers and route the checked bags appropriately.)
As for the carry on charges, if I understand correctly their policy is basically: if you purchase a ticket through a third party to whom we have to pay a commission, you have to pay extra fees. If you purchase it directly from us, you don't. Hmm… It's clearly about money, but it sounds to me like a way to get around price-matching guarantees with third party price comparison sites.