Unfortunately today MANY companies include key rate changes in fine print buried in your monthly statement. If you look closely at your checking statement or phone bill, you'll notice lots of fine print, usually about stuff like calling between New Zealand and New Foundland being no longer discounted on Queen's Day, totally irrelevent to you. But buried in such notices are rate changes that are significant to you.
I bet if you got a magnifying glass and checked your past AT&T bills or inserts you'll find such notice some months ago.
Anyway, I suggest calling them up and complaining strongly. If they don't waive the charges, dump them and get someone else. (Others will probably charge similar to AT&T though). Local companies provide LD now and I'm satisified with mine though my needs are different.