Yeah that sucks that Frontier didn't give any notice, it should have even though technically rules are subject to change at anytime. However many airlines charge to change award tickets regardless of when the flight is. About the Frontier Mastercard, you shouldn't have canceled it as the no annual fee card will still give you the waiver and in alot of cases canceling your credit card has a negative effect on your FICO score.